Reachable Nodes

Easy
0/40
Average time to solve is 10m
5 upvotes
Asked in companies
DirectiAmazon

Problem statement

You are given a graph with ‘N’ nodes and ‘M’ unidirectional edges. Your task is to find the number of nodes reachable from node ‘i’, where 0 <= ‘i’ <= ‘N’ - 1.

Note: A node ‘u’ is said to be reachable from node ‘v’, if there exists a path between node’ u’ and ’v’.

For example:

For given N = 4, M = 4,

1

In the above example, the number of nodes reachable from nodes 0 , 1, 2 and 3 is 4.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains one positive integer ‘T’, denoting the number of test cases, then ‘T’ test cases follows.

The first line of each test case contains two integers ‘N’ and  ‘M’, denoting the number of nodes and the number of edges.

The next ‘M’ lines of each test case contains two space-separated integers ’u’ and ‘v’, denoting the edge between ‘u’ and ‘v’.
Output Format: 
The first line of each test case contains an ‘N’ space separated integer, denoting the number of nodes reachable from node ‘i’, where 0 <= ‘i’ <= ‘N’ - 1.

Output of each test case will be printed on 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 <= T <= 5
1 <= N, M <= 10 ^ 3
0 <= u, v <= N - 1 

Time Limit: 1 sec.
Sample Input 1:
2
4 4
0 1
1 2
1 3
2 3
5 3
0 1
1 2
3 4
Sample Output 1:
4 4 4 4
3 3 3 2 2
Explanation of Sample Output1:
In the first test case, the graph like this:

1

As we can observe, The number of reachable nodes from node 0 is 4, i.e 0 to {0, 1, 2, 3}. Also the graph is completely connected. Therefore, all the nodes can be reached from all the other nodes. Hence, the answer is {4, 4, 4, 4}. 

In the second test case, the graph looks like this:

1

As we can observe, there are two disconnected graphs - {0, 1, 2} and {3, 4}. Therefore, The number of reachable nodes from nodes 0,1 and 2 is 3 and from nodes 3 and 4 is 2.
Sample Input 2:
2
5 4
0 0
0 1
1 3
4 2
2 2
0 0
1 1
Sample Output 2:
3 3 2 3 2
1 1
Hint

Can you perform dfs traversal from each node to count the number of nodes reachable from each node?

Approaches (2)
DFS traversal

  The idea is very simple: we will perform dfs from each node and count the number of nodes in that particular component.

 

Algorithm:

 

The steps are as follows:

 

  • Take the following global variables:

2D array ‘Graph’, to store graphs.

‘Visited’ array to mark each node whether it is visited or not.

 

Let ‘countNodes(n, m, edges)’ be the function that counts the number of nodes reachable from each node. It returns the array of size n.

 

  • Clear graph, initialize the visited array to false.
  • Run a loop from 0 to 'm' :
    • Add the undirected edge between edges[i] [0] and edges[i][1].
  • Take an array 'ans' to store the answer.
  • Run a loop from 0 to 'n'.
    • Perform a dfs call and store the return value in variable ‘count’ i.e count = dfs(i).
    • Store ‘count’ at ‘ans[i]’.
    • Mark visited node 'i' to false for the next dfs call.
  • Return ‘ans’.

 

Description of dfs(n) function

 

  • Mark visited[s] equal to true.
  • Take a variable ‘count’ and initialize it to 0.
  • Travel through its adjacents and store the current adjacent in variable ‘adj’.
    • If visited[adj] is false.
      • Update the count of nodes in this component i.e count += dfs(adj).
  • Return ‘count’ + 1.
Time Complexity

 O(N * (N + M) ), where ‘N’ is the number of nodes and ‘M’ is the number of edges.
 

We are performing dfs which take O(N + M) for each ‘N’ node. So the total time complexity is O(N * (N +M)).

Space Complexity

O(N + M), where ‘N’ is the number of nodes and ‘M’ is the number of edges.

 

Mainly, we are using space for creating a graph which takes O(N + M).

Code Solution
(100% EXP penalty)
Reachable Nodes
Full screen
Console