2. Social Networking Graph

Spoj Question

In a social networking site, people are connected with other people. The whole system appears as a giant connected graph. In this question, you are required to answer the total number of people connected at t nodes away from each other (t distance connectivity).

Solution : (Using BFS)

#include <bits/stdc++.h>

using namespace std;

int bfs(int node, vector<int> v[], vector<bool> vs, int dist)
{
    int c = 0;
    queue<int> q;
    q.push(node);
    vs[node] = 1;
    while (!q.empty())
    {
        c++;
        int s = q.size();
        while (s > 0)
        {
            int x = q.front();
            vs[x] = 1;
            q.pop();

            for (auto itr = v[x].begin(); itr != v[x].end(); itr++)
            {
                if (vs[*itr] == 0)
                {
                    q.push(*itr);
                    vs[*itr] = 1;
                }
            }
            s--;
        }
        if (c == dist)
        {
            break;
        }
    }
    return q.size();
}

int main()
{
    int n, e;
    cin >> n >> e;
    vector<int> v[n + 1];
    vector<bool> vs(n + 1);

    for (int i = 1; i <= e; i++)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    int q;
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        int node, dist;
        cin >> node;
        cin >> dist;
        int x = bfs(node, v, vs, dist);
        cout << x << "\n";
    }

    return 0;
}

Time Complexity: O(V+E)