Tarjan – 求解有向图的强连通分量 (SCC)

Robert E Tarjan是一个神人。

1.关于出栈怎么写

2.关于 Case 2 （牵扯Low定义的问题） 为什么不能改为

StackOF上面给了一个证明，这里引述一下。

In tarjan’s dfs search getting lowlink(u):

lowu=min(low, low) (v isn’t visited)

or

lowu=min(low, dfn) (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 dfn<= lowv <= dfnv. The second is that, when determining whether v is a root, we have for all w reachable from v that low<= 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’<= low<= dfnw.

I imagine that the algorithm is presented the way it is to avoid the need to consider intermediate values of low.

tarjan算法中low的标准定义是low= min ( dfnu , lowv , dfnw );

3.