我有向图G（V，E）。 G可能包含循环。每个v以值n [v]开头。让我们称S {v}为G中v可以到达的所有顶点。对于每个v，我需要用max（n [u]），u∈S{v}更新n [v]。
我尝试使用具有路径压缩的快速联合
，但因为G是有向图，所以我不能。一个选项是在每个节点上使用DFS，但在最坏的情况下，复杂度将为O（V（V + E））。
是否有更好的方法（也许使用拓扑排序，可传递约简或强连接的组件）？
我有向图G（V，E）。 G可能包含循环。每个v以值n [v]开头。让我们称S {v}为G中v可以到达的所有顶点。对于每个v，我需要用max（n [u]），u∈S{v}更新n [v]。我是...
是，O（V + E）有更好的方法：