有向图(|V|=a, |E|=b)给出。
每个顶点都有特定的权重。我们想要每个顶点(1..a)找到从该顶点可以到达的具有最大权重的顶点。
更新 1：@Paul 在 O(b + a log a) 中准备了一个很好的答案。但是我
搜索 O(a + b) 算法（如果有）？
有没有其他有效或最快的方法来做到这一点？
是的，可以修改 Tarjan 的 SCC 算法来在线性时间内解决这个问题。
Tarjan 的算法使用两个节点字段来驱动其 SCC 查找逻辑：index，表示算法发现节点的顺序；和lowlink， 最低index通过一系列树弧和后面的弧可以到达。作为同一深度优先遍历的一部分，我们可以计算另一个字段，maxweight，它具有以下两种含义之一：
计算逻辑maxweight如下。如果我们发现一条弧v到一个新节点w, then vw是一个树弧，所以我们计算w.maxweight递归并更新v.maxweight = max(v.maxweight, w.maxweight). If w在堆栈上，那么我们什么都不做，因为vw是一个后弧并且不包含在定义中maxweight。否则，vw是一个交叉弧，我们对树弧进行相同的更新，只是没有递归调用。
当Tarjan的算法识别出SCC时，是因为它有一个节点r with r.lowlink == r.index. Since r是该SCC的深度优先搜索根，其值为maxweight对于整个 SCC 来说是正确的。我们不记录 SCC 中的每个节点，而是简单地更新其maxweight to r.maxweight.
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
