Find the highest reachable node from each node

Question

I have a directed graph G(V,E). G may contain cycles. Each v starts with a value n[v]. Lets call S{v} all vertices reachable by v in G. For each v, I need to update n[v] with the max(n[u]), u∈S{v}.

I've tried using Quick-Union with path compression, but I can't because G is a directed graph.

An option is using DFS on each node, but the complexity would be O(V(V+E)) in the worst case.

Is there a better way to approach it (maybe using topological sorting, transitive reduction or strongly connected components)?

Answer 1

Yes there's a better way O(V+E):

1. Find all strongly connected components (Kadane or Tarjan algorithms) and save max_n[v] for each vertex in component
2. build a new graph out of strongly connected components
3. new graph is a DAG
4. use DP to calculate required values for each component (for DAG`s its either top down with DFS or bottom up with Kahn)