All Tracks Algorithms Graphs Breadth First Search Problem

Social Networking Graph
/
No tags
Problem
Editorial
Analytics

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). For example: Two persons directly connected are at 1 distance connectivity. While the two persons having a common contact without having direct connectivity, are at 2 distance connectivity.

First line of input line contains, two integers n and e, where n is the nodes and e are the edges. Next e line will contain two integers u and v meaning that node u and node v are connected to each other in undirected fashion. Next line contains single integer, m, which is number of queries. Next m lines, each have two inputs, one as source node and other as a required t distance connectivity which should be used to process query.

 

Note: The index of nodes will be 0-based. The example and the test case shown is of 1-based index. For submitting the solution, use 0-based indexing.

SAMPLE INPUT
9 10
1 2
2 3
1 7
2 4
3 4
4 7
7 8
9 7
7 6
5 6
3
4 2
5 3
2 1
SAMPLE OUTPUT
4
4
3
Explanation

After creating the graph, there was 3 queries,

  1. Source node: 4, and we have to find out total number of nodes at a distance of 2 from node 4.

1(4->2->1), 8(4->7->8), 9(4->7->9), 6(4->7->6) = 4

  1. Similarly as above
  2. Source node: 2, and we have to find out total number of nodes at a distance of 1 from node 2.

1(2->1), 4(2->4), 3(2->3) = 3

 

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

Initializing Code Editor...
Notifications
View All Notifications

?