我是一名学习算法信息学奥林匹克竞赛的大四学生，这是我关于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]在第二个情况?我知道这是不正确的，但我找不到反例。有人能解释一下吗?
thx:)
其实是对的。
正确的证明依赖于low的两个性质。首先，对于所有v，存在从v可以到达的w，使得dfn[w] <= low[v] <= dfn[v]。第二个是，当确定v是否是根时，对于从v可访问的所有w, low[v] <= dfn[w] .
我们可以归纳证明第一个性质仍然成立，如果存在从u到v的路径和从v到w的路径，则存在从u到w的路径。至于第二个，让low为原始数组，low'为您的数组。不难看出，对于所有v，在任何时候，low'[v] <= low[v]，所以在v的关键时刻，对于所有从v可达的w, low'[v] <= low[v] <= dfn[w] .
我认为该算法的呈现方式是为了避免需要考虑low的中间值。