Last Updated: 4 Dec, 2020
Reachable Nodes
Easy
Asked in companies
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,
In the above example, the number of nodes reachable from nodes 0 , 1, 2 and 3 is 4.
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.
Approaches
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).
- If visited[adj] is false.
- Return ‘count’ + 1.
The idea is very simple: we will perform a single dfs and keep track of the component number to which each node belongs and the count of the number of nodes in each component.
Algorithm:
The steps are as follows:
- Take the following global variables:
- 2D array ‘Graph’, to store graph.
- ‘Visited’ array to mark each node whether it is visited or not.
- Array ‘nodeComponent’ to track component number to which ‘ith’ node belongs.
- Array ‘componentCount’ to count the number of nodes in ‘ith’ component.
- An integer ‘component’.
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 visited array to false, initialize ‘nodeComponent’ to -1, initialize ‘componentCount’ to 0 and ‘component’ to 0.
- Run a loop from 0 to 'm' :
- Add the undirected edge between edges[i ][0] and edges[i][1].
- Run a loop from 0 to 'n':
- If vertex ‘i’ is not visited.
- Perform dfs call and store the return value in variable ‘count’ i.e count = dfs(i).
- Store the count of nodes in ‘componentCount’ array for that particular component.
- Increment ‘component’ by one.
- If vertex ‘i’ is not visited.
- Take an array 'ans' to store the answer.
- Run a loop from 0 to 'n':
- Store the ‘componentCount’ of nodeComponent[i] in ‘ans[i]’ i.e ans[i] = componentCount[nodeComponent[i]].
- Return ‘ans’.
Description of dfs(n) function
- Mark visited[s] equal to true.
- Take a variable ‘count’ and initialize it to 0.
- Store ‘component’ in ‘nodeComponent[s] ‘.
- 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).
- If visited[adj] is false.
- Return ‘count’ + 1.