algorithm - 关于tarjan的查找scc的算法

Question

我是一名在算法方面学习信息学奥林匹克的大四学生，这是我在 stackoverflow 上的第一个问题。

在 tarjan 的 dfs 搜索中得到lowlink(u)：

low[u]=min(low[u],low[v])（v 未访问）

或者

low[u]=min(low[u],dfn[v])（v仍在堆栈中）

我的问题是，在第二种情况下将dfn[v]替换为low[v]是否仍然可以？我知道这是不正确的，但我找不到反例。谁能帮忙解释一下？

谢谢：）

Answer 1

其实是对的

正确性的证明取决于 的两个属性low。第一个是，对于所有人v来说，存在从这样的w可到达的。第二个是，当确定是否是一个根时，我们有所有可到达的。vdfn[w] <= low[v] <= dfn[v]vwvlow[v] <= dfn[w]

我们可以通过以下事实归纳证明第一个性质仍然成立，如果有一条 from utov和一条 from vto w，那么就有一条 from uto w。至于第二个，让low原始数组low'成为你的。不难证明，对于所有v，在任何时候，low'[v] <= low[v]，所以在关键时刻对于v，对于所有w可到达的v，它都持有low'[v] <= low[v] <= dfn[w]。

我想算法的呈现方式是为了避免需要考虑low.