有向图的强连通分量是一个极大强连通子图。一个强连通子图是一个节点集合，使得集合中的任意两个点互相可达。本文介绍有向图强连通分量的tarjan算法，并且提供了理解tarjan算法所需要的前置DFS知识。
直观上来讲，tarjan算法对有向图建立搜索树，每一个连通分量都是该搜索树的一棵子树。在无向图中查找连通分量时，我们常借助于dfs，那么在有向图查找强连通分量时，我们也使用了借助于dfs的tarjan算法。tarjan算法由一个dfs构成，在dfs过程中，将访问过的节点压入一个栈中，栈顶到栈中的的某个元素构成一个极大强连通分量。

DFS相关知识补充

相对于先前简单的 $vis$ 数组，首先要介绍DFS的黑白灰染色法，我们规定当节点未被发现时为白色，被发现后为灰色，在它的所有邻接链表被扫描完毕后为黑色。从白到灰的时间点为d，从灰到黑的时间点为f。使用黑白灰染色法能够方便我们进行下面的讨论。
tarjan算法基于DFS，从任意一点$p$开始遍历，在DFS的过程中会形成一棵树或者森林，称为DFS树。假如从点$u$访问到一个尚未被访问的点$v$，那么边$(u, v)$是一条树边，体现在DFS上就是$v$是$u$的儿子。同理，紧接着从$v$继续DFS到另一个未发现的点$w$，那么边$(v, w)$也是一条树边。下面回到节点$u$，现在发现从$u$居然还有一条直接到$w$的边，这里的边$(u, w)$称为前向边，可惜在DFS时所有的前向边都不会体现在DFS树中，这是因为此时$vis[w]$必然为true，因此$w$是$u$的非儿子的后代。我们考虑刚才的前向边$(u, w)$，此时$u$为灰色，因为它访问的$w$节点还没有返回；$w$为黑色，$v$也是黑色，因为它的dfs已经返回了。下面我们考虑在此之前的一个情况，当$w$还是灰色的时候，它应该已经在$u$之前发现过$(u, w)$这条边了，但是这时候$u$和$w$都是灰色，这种情况就和上面之前看到的前向边不一样了，我们称他为后向边。

后向边是一个非常有用的东西，它可以用来发现环和计算下面的强连通分量。我们还需要注意到后向边的一个性质，也就是$u.d < w.d$，这是显然的。除此之外，还有一种横向边，不过所幸DFS中只会出现树边和后向边。

括号化定理

在对有向图或者无向图DFS的过程中，对于任意节点u和v，只有一种情况成立：

[u.d, u.f]和[v.d, v.f]完全分离
这说明u和v互不为对方的后代
[u.d, u.f]完全包含在[v.d, v.f]中
[v.d, v.f]完全包含在[u.d, u.f]中

白色路径定理

v是u的后代，当且仅当在u.d时，存在一条从u到v的全部由白色节点构成的路径。

无向图DFS定理

在对无向图进行DFS时，每条边要么是树边，要么是后向边。

判环

一个有向图G无环，当且仅当对其DFS时不产生后向边。

tarjan算法原理

我们容易发现可以把一个强连通分量看成搜索树中的一棵子树。我们在DFS的过程中不断将我们发现的节点加入一个堆栈，这个栈其实也对应这DFS的递归。
算法需要$dfn[u]=1..vertex\_count$记录对节点$u$的访问次序，对应着算法导论中的属性$u.d$，即该节点从白变灰的时间戳，记录这个次序主要是为了处理后向边。

$low[u]$记录节点$u$的最早祖先，它表示$u$或$u$的子树能够追溯到的最早的还在栈中的节点的时间戳，我们在将一个节点由灰标黑时计算该节点对应的$low$值。显然，在遍历前我们要设置初始的$dfn[u]$和$low[u]$等于时间戳$index$。当遍历后仍然是$dfn[u]==low[u]$时，$u$不存在可到达的祖先了，得到极大强连通分量。此时$u$也作为这个子树的根（并查集也有类似的性质）。这时我们考察堆栈，根离栈顶最远，永远在最后被弹出。

$low[u]$在三种情况下更新：

当存在树边$(u, v)$时，应当尝试用$low[v]$更新$low[u]$。这种情况发生在节点$u$发现一个白色节点$v$的时候，此时首先会递归地调用dfs来计算$v$节点，当$v$节点的遍历完成也就是变黑后，dfs返回到我们在$u$节点的调用处，这时候我们尝试用$low[v]$和$low[u]$之间的较小值更新$low[u]$。因此$low[v]$总是先于$low[u]$被更新，可以通过$dfn[v]$是否为0判断$v$是否被访问过
当存在后向边$(u, v)$时，当此时 $v$还在栈中时，应当尝试用$dfn[v]$更新$low[u]$，这里自环也被认作后向边。这里必须要判断在$v$是否在栈中，因为$v$可能已经是个黑色节点了，这时$(u, v)$是一条横向边。

因此可以得到$low[i]$的过程

def tarjan(u)
    for each (u, v) in E // 遍历所有的边(u,v)
        if (!dfn[v]) // 如果v没被访问过，则(u,v)是树边
            // 注意一定要先进行dfs
            tarjan(v);
            low[u] = min(low[u], low[v])
        else if(v exist in stack) // 如果v是个灰色节点，则(u,v)是后向边
            low[u] = min(low[u], dfn[v])
        // 否则v属于另一个连通分量已被弹出

下面是整个tarjan算法

void tarjan(int u){
    dfn[u] = low[u] = ++index;
    stack.push(u);
    update low[u] // 整合上面的循环
    if(dfn[u] == low[u]) // 注意不要把if写在update的for each循环里面
        pop stack to u // 注意是u不是dfn[u]
}
int main(){
    zero(dfn);
    for each u in V
        if(!dfn(u))
            tarjan(u)
}

可以看到算法对于每个点都访问一次，由dfn(u)!=0保证，同样，对每个边$(u, v)$都访问一次。

割点与桥

求割点和桥是tarjan算法的一个经典应用。

LCA Tarjan

这里的LCA Trajan是一种离线算法，它首先先要进行$O(n)$得到预处理。它的思路是第一次找到两个节点的时候，如果记录了他们的深度最大的单亲节点，那么该节点就是LCA。

下图算法中，FIND-SET类似于find，找到并查集的根，类似于一种路径压缩。UNION类似于merge。

我们在查询LCA(u,v)时，假如u已经被遍历过，现在在处理v，那么此时LCA(u,v)一定是灰色的。如果在dfs完u后(u变黑时)，对u的所有孩子x执行merge(u,x)，将u设置为x的父亲。那么在准备把v也变黑之前，find(u)就是要找的LCA。
这里可能会有疑惑，为什么find找到最根部的father，一定是深度最小的，而不是深度最大的呢？原因很简单，我们在u刚变黑的时候，才将u加入并查集的。这个时候，v应该还是白色。反证下，假定找的这个LCA1并不是最深的，最深的是LCA2，那么LCA1是LCA2、u、v的祖先。那么当u变黑的时候，LCA1和LCA2都是灰色，u会把自己的并查集挂在LCA2上。注意此时不会到LCA1上，因为LCA2还没变黑，只有当它变黑的时候，u、LCA2才会认LCA1这个祖先。后面就显然了，遍历到v的时候，LCA2还是灰色的呢，所以最终LCA2才是LCA。