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.
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)
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 but the time complexity is looking efficient.
Brother I don’t know about any contest. I was just learning graph theory.