Tarjan的理解

Tarjan算法基于定理：在任何深度优先搜索中，同一强连通分量内的所有顶点均在同一棵深度优先搜索树中。也就是说，强连通分量一定是有向图的某个深搜树子树。 根据Tarjan: low(u)=min(dfn(u),(low(v),u与v相连且v在栈中)) 其实low(u)是表示u所在的强连通分量的根的dfn值。 易知强连通分量是由许多环组成，在深搜中遇到环时，换句话说，遇到一个点已经被搜索过，也就是在栈中，我们把这个环的low值全部更新为最小的（为何最小？因为强连通分量的根是这个强连通分量中所有元素中最早入栈的，所以dfn(遍历序号）也是最小的），也就是这个环的根的dfn值。 重复这个过程，可以把强连通分量求出，并且这个强连通分量的所有点得low值为强连通分量的根的dfn值。 当回溯到根时，假设根的为u，因为其low值也为强连通分量的根的dfn值，所以low(u)=dfn(n)时，找到强连通分量的根，这个强连通分量搜索完毕，输出此强连通分量：把从根到栈顶所有元素输出即可。