Bishu and his Girlfriend

There are N countries {1,2,3,4....N} and N-1 roads(i.e depicting a tree)

Bishu lives in Country 1 so this can be considered as the root of the tree.

Now there are Q girls who lives in various countries (not equal to 1) .

All of them want to propose Bishu.But Bishu has some condition.

He will accept the proposal of the girl who lives at minimum distance from his country.

Now the distance between two countries is the number of roads between them.

If two or more girls are at the same minimum distance then he will accept the proposal of the girl who lives in a country with minimum id.

No two girls are at same country.

Example:

Input:  n = 6, edges = {{1, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}}, q = 4, queries = {5, 6, 3, 4}
Output: 3

Approach

C++

#include <bits/stdc++.h>
using namespace std;
vector<int> arr[1001];
int vis[1001];
int dist[1001];
void bfs(int src)
{
    queue<int> q;
    q.push(src);
    vis[src] = 1;
    dist[src] = 0;
    while (!q.empty())
    {
        int curr = q.front();
        q.pop();
        for (int child : arr[curr])
        {
            if (vis[child] == 0)
            {
                vis[child] = 1;
                dist[child] = dist[curr] + 1;
                q.push(child);
            }
        }
    }
}
int main()
{
    int n = 6;

    vector<vector<int>> edges = {{1, 2},
                                 {1, 3},
                                 {1, 4},
                                 {2, 5},
                                 {2, 6}};
    for (int i = 0; i < edges.size(); i++)
    {
        int a = edges[i][0], b = edges[i][1];

        arr[a].push_back(b);
        arr[b].push_back(a);
    }
    int q = 4;
    vector<int> queries = {5, 6, 3, 4};
    bfs(1);
    int ans, min1 = INT_MAX;
    for (int i = 0; i < q; i++)
    {
        int x = queries[i];

        if (dist[x] < min1)
        {
            ans = x;
            min1 = dist[x];
        }
    }
    cout << ans << "\n";

    return 0;
}