Robert E Tarjan是一个神人。
} while (cache2!=u);
2.关于 Case 2 （牵扯Low定义的问题） 为什么不能改为
else if(instack[v]==true) low[u]=min(low[u],dfn[v]);
可以看一下StackOverFlow ，和 POJ的 One Way Traffic这道题
In tarjan’s dfs search getting lowlink(u):
lowu=min(lowu , lowv ) (v isn’t visited)
lowu=min(lowu , dfnv ) (v is still in the stack)
My question is, is it still ok to replace dfnv for lowv in the second case? I know this is incorrect, but I failed finding a counter-example. Could anyone help explain this?
It’s correct, actually.
The proof of correctness depends on two properties of low. The first is that, for all v, there exists w reachable from v such that dfnw <= lowv <= dfnv. The second is that, when determining whether v is a root, we have for all w reachable from v that lowv <= dfnw.
We can prove inductively that the first property still holds by the fact that, if there’s a path from u to v and a path from v to w, then there’s a path from u to w. As for the second, let low be the original array and low’ be yours. It’s not hard to show that, for all v, at all times, low’v <= lowv, so at the critical moment for v, for all w reachable from v, it holds that low’v <= lowv <= dfnw.
I imagine that the algorithm is presented the way it is to avoid the need to consider intermediate values of low.
tarjan算法中low的标准定义是lowu = min ( dfnu , lowv , dfnw );