How to efficiently find list of reachable nodes from a node in a directed graph

how to efficiently find list of reachable nodes from a node in a directed graph

You can use DFS.

but @codesfit if i have V nodes, then dfs for every pair of nodes will take O( (V+E)VV ) time.
I want better than this.

O( (V+E) *V * V )

It will be \mathcal{O}((|V| + |E|) \times |V|). Each dfs will tell you the reachable list of each node.

1 Like

Is there any better solution than this in terms of time complexity ?

Nope if u wanna find all reachable nodes then u have to do DFS from each of node .
Is this question is from any ongoing or past challenge ? If yes then please share link , so that we will submit code check whether the above logic works or not .

If you really want to overkill, then you can create a DAG out of the SCC in the graph, and then make a topological sort.

Process from last to first and then use a bitset or to combine the answers. If something is reachable from u, then it’s either u itself or something it can reach from v where there is an edge from u to v. So you can take the bitwise or of the reachable bitmask of each v.

The time complexity is O(|V||E|/64)

1 Like

It’s the first question from the facebook hackercup contest. The simplified version of the question is basically for each pair of nodes i & j, find if you can reach j from i given a directed graph. Ideally you should discuss the questions once the contest is over.

could not understand :smiley: but the time complexity is looking efficient.

Brother I don’t know about any contest. I was just learning graph theory.