Last Updated: 10 Jan, 2021
Social Networking Graph
Moderate
Asked in companies
You are given a graph with 'N' nodes numbered 1 to 'N', and 'E' edges, and you have to solve 'M' queries. Each query consists of two integers 'S' and 'T'. Your task is to find the count of nodes that are at a distance of 'T' from the node 'S'.
Two nodes that are directly connected with each other are considered to be at a distance of 1 unit. While two nodes having a common contact without having direct connectivity, are considered to be at a distance of 2 units. In a similar manner, we can calculate distances between nodes.
Note:
The graph may contain cycles.
Input Format:
The first line of each test case contains two space-separated integers 'N' and 'E', the number of nodes and edges in the graph respectively.
The following 'E' lines contain two space-separated integers 'U' and 'V', denoting an undirected edge between the nodes 'U' and 'V'.
The next line contains an integer, 'M', denoting the number of queries.
Then 'M' lines follow:
Each line consists of two integers 'S' and 'T', where 'S' denotes the source node, and 'T' denotes the connectivity distance to be processed.
Output Format:
For each query, print a single line containing a single integer denoting the count of nodes as asked in the problem statement.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= N <= 3 * 10 ^ 3
1 <= E <= 10 ^ 4
1 <= U, V <= N
1 <= M <= 100
1 <= S <= N
1 <= T <= 2500
Time Limit: 1 sec.
Approaches
It’s clearly visible that we need to traverse the graph optimally in order to get our answer.We will use Breadth First Search to achieve this. Let’s understand how to do this.
- We will start by making our graph. We can do this by making a unordered_map and push our nodes inside that map.
- Now our graph is made and now we will head over to answer our m queries. We will start by making a socialNetwork() function, in which we will pass our source node(s), the distance connectivity(t), the number of nodes(n) and our graph.
- Inside the function we will make a visited array(visited[]) of n + 1 size and assign a value of 0 to all its elements, which means they are not visited. We will also make an integer variable count(initialized to be 0), which will store our answer.
- Now let’s make a queue and push our source inside and also make visited[source] = 1, which means we have visited our source.
- Now we run a loop till our queue is empty. Inside this loop we will assign the value of the front of the queue to another integer variable named node and we will pop this node from the queue, and we will check if visited[node] is equal to t + 1, if this condition is met, then we increment count by 1.
- Now we will run a loop to traverse all the children of this node.. And if the child has not been visited yet then push the child node into the queue, and update visited[child] = visited[node] + 1.
- Once this loop is exited. Once the queue becomes empty we return count, which is our answer.
- We do this for all m queries to reach our final answer.