Number of nodes reachable from each node in a directed graph

Revision en1, by vaibnak7, 2020-07-26 21:57:46

Given a directed graph, suppose we want to find the number of reachable nodes from each node of the graph then what is the best way to solve this problem ??

One obvious way to solve it is doing dfs from every node of the graph and counting how many nodes are getting visited, but the problem with this approach is that it is O(n^2) where n is the number of nodes in the graph

Then i thought of maybe if we can store at each node how many nodes are reachable and when queried give the answer based on the values of the neighbouring nodes but this will not be able to handle the case of overcounting as in the graph below.

So how to solve this ?

Tags #graph, directed, #dfs

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English vaibnak7 2020-07-26 21:57:46 785 Initial revision (published)