在有向图中，如果点 \(u\) 和点 \(v\) 可以互相到达，我们就可以称 \(u,v\) 是强联通。
强联通分量就是极大的强联通子图，使得 \(u \in S,v \in S\) 都有 \(u,v\) 为强联通关系。
DFS 生成树
在介绍该算法之前，先来了解 DFS 生成树，我们以下面的有向图为例：
有向图的 DFS 生成树主要有 4 种边（不一定全部出现）：
- 树边：示意图中以黑色边表示，每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。
- 反祖边：示意图中以红色边表示（即 \(7 \to1\)），也被叫做回边，即指向祖先结点的边。
- 横叉边：示意图中以蓝色边表示（即 \(9 \to 7\)），它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点 并不是 当前结点的祖先。
- 前向边：示意图中以绿色边表示（即 \(3 \to 6\)），它是在搜索的时候遇到子树中的结点的时候形成的。
我们考虑 DFS 生成树与强连通分量之间的关系。
如果结点 \(u\) 是某个强连通分量在搜索树中遇到的第一个结点，那么这个强连通分量的其余结点肯定是在搜索树中以 \(u\) 为根的子树中。结点 \(u\) 被称为这个强连通分量的根。
反证法：假设有个结点 \(v\) 在该强连通分量中但是不在以 \(u\) 为根的子树中，那么 \(u\) 到 \(v\) 的路径中肯定有一条离开子树的边。但是这样的边只可能是横叉边或者反祖边，然而这两条边都要求指向的结点已经被访问过了，这就和 \(u\) 是第一个访问的结点矛盾了。得证。
Tarjan 求SCC
我们需要在 \(dfs\) 上算出 \(SCC\)。
首先还是老两样。
我们定义 \(dfn_i\) 表示 \(dfs\) 序，\(low_i\) 在 \(i\) 的子树中可以通过非树边回溯到的最小的 \(dfn\) 的点。
我们使用一个栈记录我们搜索过的元素。对于和当前的点 \(u\) 相邻的点 \(v\) (不是父亲) 我们只会有三种情况。
\(1.\) 没访问过。我们继续访问点 \(v\) 。在回溯的时候 \(low_u=\min(low_u,low_v)\)。原因显然，\(u\) 既然可以都 \(v\)，那 \(v\) 可以到的 \(u\) 也一定可以到。
\(2.\) 访问过，在栈里面。显然我们此时找到了一条非树边，我们需要用 \(dfn_v\) 更新 \(low_u\)，这时候其实就已经 \(u,v\) 之间的点构成强联通了。
\(3.\) 访问过，不在栈里面。我们不管。
记得出栈就可以了。
如何判断一个点是不是 \(SCC\) 的根节点也很简单。对于点 \(u\)，如果有 \(dfn_u =low_u\),也就是说他无法到达比他更早的点，他是第一个搜索到的节点，根据前面的定义可得。
回忆一下？
如果结点 \(u\) 是某个强连通分量在搜索树中遇到的第一个结点，那么这个强连通分量的其余结点肯定是在搜索树中以 \(u\) 为根的子树中。结点 \(u\) 被称为这个强连通分量的根。
有了这些储备知识，我们就可轻而易举的写出一份代码了。