一下许多内容摘自： 北京大学暑期课《ACM/ICPC竞赛训练》强连通分支、桥和割点 北京大学信息学院 郭炜
不建议初学者直接看这篇博文 可以先了解一下Tarjan算法的具体流程，再来看证明。 推荐：全网最!详!细!tarjan算法讲解
如果有向图G的每两个顶点都强连通，称G为强连通图。 非强连通图有向图的极大强连通子图，称为强连通分量。
DFN[i]表示 遍历到 i 点时是啥时候（DFS过程中的访问序号）。 所以DFN[i]越小，就说其越“早”。 LOW[i]表示从i节点出发 DFS过程中 i下方节点v 1 （开始时间大于DFN[i]，且由i可达的点）所能到达的最早节点的开始时间。DFS过程中，碰到哪个节点，就将哪个节点入栈。栈中节点只有在其所属的强连通分量已经全部求出时，才会出栈。 对于u的子节点v，从v出发进行的DFS结束回到u 时，使得 LOW[u] = min(LOW[u],LOW[v])。因为u可达v, 所以v可达的最早的节点，也是u可达的。 如果发现某节点u 有边连到栈里的节点v 2 ，则更新u的LOW值为min(LOW[u],DFN[v]) ，若LOW[u]被更新为DFN[v],则表明目前发现u可达的最早的节点是v. （注意v在栈中，v比u先被访问到） 如果一个节点u，从其出发进行的DFS已经全部完成并回到u，而且此时其LOW值等于DFN值，则说明 u可达的所有节点，都不能到达任何比u早的节点 — 那么该节点u就是一个强连通分量在DFS搜索树 中的根。那么现在将栈中u及u上方的节点全部弹出，弹出的节点构成一个强连通分量。 伪代码：
void Tarjan(u) { dfn[u]=low[u]=++index stack.push(u) for each (u, v) in E { if (v is not visted) { tarjan(v) low[u] = min(low[u], low[v]) } else if (v in stack) { low[u] = min(low[u], dfn[v]) } } if (dfn[u] == low[u]){ //u是一个强连通分量的根 repeat v = stack.pop print v until (u== v) } //退栈，把整个强连通分量都弹出来 } } //复杂度是O(E+V)的为什么从u出发的DFS全部结束回到u时，若 dfn[u]=low[u], 此时将栈中u及其上方的节点 弹出，就找到了一个强连通分量? 强连通分量的特性：有向边，任意两个节点都可以相互到达。 此时所有节点分成以下几类： 1)还没被访问过的节点 2) 栈中比u早的节点(在u下方) 3) 栈中比u晚的节点(在u上方) 4) 栈中的u 5) 曾经入栈（访问过），又出了栈的节点 证明： 1)：显然由u不可达。 2)：由u不可达，因为DFN[u] = LOW[u]; u怎么转，能到达最早的点只有自己。 3)：u可达此类节点，且这类节点可达u。 u可达此类节点是显然的。 证：此类节点可达u 若有此类节点x不可达u，首先不存在有向边(x->u)，寻找x所能到达的最早的: 1.如果就是x，low[x]=dfn[x]，则x应该已经被弹出栈了，这和x是第3类节点矛盾。 2.栈里面的节点y，则y必然比u晚，因为dfn[u]=low[u]，u最早能到达的点为其本身，y比u早，则是y。而且有 low[y] = dfn[y]（若此条不成立，则x还能到达比y更早的节点，矛盾）。而若 low[y] = dfn[y]，则y应该已经被弹出栈了，y上方的x当然也已经不再栈中，这和x是第3类节点矛盾。 4)：略。 5)：这类节点不可达u 1.早于u遍历到，早于u的出栈即证明不可达u。 若可达的话，它此时应该还在栈里面，u的下面 —导致矛盾。 2.晚于u遍历到，任取节点x,假设x可达的最早节点是y，则y一定晚于u, 即 x不可达u. 任取节点x。x之所以已经被弹出栈，一定是 因为最终low[x] = dfn[x]，或x位于某个y节点上方， 由y可达,且y满足条件:最终的 low[y] = dfn[y]。 因为y曾经出现在u的上方，所以y一定晚于u。因为 low[x]不可能小于等于dfn[u](否则low[y]就也会小于等于dfn[u],这和low[y]=dfn[y]矛盾），所以x到达不了u及比u早的节点。
That’s all, thanks! 推荐： Tarjan求桥和割点与双连通分量
