algorithm - 从每个节点中找到最高可达的节点

Question

我有一个有向图 G(V,E)。 G 可能包含循环。每个 v 以值 n[v] 开头。让我们将 G 中 v 可达的所有顶点称为 S{v}。对于每个 v，我需要用 max(n[u]), u∈S{v} 更新 n[v]。

我试过使用 带路径压缩的 Quick-Union ，但我不能，因为 G 是有向图。

一个选项是在每个节点上使用 DFS，但在最坏的情况下复杂性将是 O(V(V+E))。

有没有更好的方法来处理它(可能使用拓扑排序、传递归约或强连接组件)？

Answer 1

是的，有更好的方法 O(V+E):

找到所有强连通分量(Kadane 或 Tarjan 算法)并保存 max_n[v]对于组件中的每个顶点

用强连通分量构建一个新图

新图是 DAG

使用 DP 计算每个组件所需的值(对于 DAG，它要么使用 DFS 自上而下，要么使用 Kahn 自下而上)