有向图的强连通分量

定义

对于一张有向图 $G = (V, E)$ ，对于两点 $u,v \in V$ ，都存在一条路径可以使得 $u$ 达到 $v$ ， $v$ 也可以达到 $u$ ，则称该两个点是互相可达的。

如果一张有向图上的任意两个节点之间可以互相可达，则称这张图是 强连通的（Strongly Connected）。

对于一张子图 $H \in G$ ，并且不存在其他的连通图 $F$ 使得 $H \notin F \in G$ ，则称子图 $H$ 是有向图 $G$ 的一个 强连通分量（Strongly Connected Component，SCC），叫做极大的连通分量。

应用

对于一个较为复杂的图论问题中，利用强连通分量的缩点技巧，将每一个强连通分量中的所有点看作一个点，最终使得图转化为 有向无环图（DAG），大大的减少了时间复杂度和解题难度。

Tarjan 算法

DFS 生成树

对于一张图的深度优先遍历，根据节点的先后遍历顺序，我们可以生成出一棵树，这棵树即为 DFS生成树，它的性质有如下几点：

深度优先遍历的第一个点是该树的根节点。
遍历一个节点的所有边时，如果找到一个没有访问过的节点，则这条边被称为树边（tree edge），如果找到了一个访问过的节点，则可能是返祖边（back edge）或者横叉边（cross edge）。除此之外，还有一种边叫做前向边（forward edge），它是在搜索的时候遇到子树中的节点的时候形成的。
如果结点 $u$ 是某个强连通分量在搜索树中遇到的第一个结点，那么这个强连通分量的其余结点肯定是在搜索树中以 $u$ 为根的子树中。结点 $u$ 被称为这个强连通分量的根。

时间戳

在 Tarjan 算法中我们引入时间戳的概念，表示着DFS生成树上遍历节点的顺序。

我们维护一下几个变量：

$dfn_u$ ：表示深度优先搜索遍历节点时节点 $u$ 的时间戳。
$low_u$ ：表示已 $u$ 为根的子树中时间戳最小的一个节点的时间戳。

因为一个节点的子树内的 $dfn$ 都大于该节点的 $dfn$ ，不难证明：

从根开始的一条路径上的 $dfn$ 严格递增， $low$ 严格非降。

Tarjan 算法

因此我们很容易想到，在一个强连通分量中，有且只有一个节点 $u$ 使得 $dfn_u = low_u$ ，这个节点也是该分量中的根节点。因此，在深度优先搜索的回溯过程中，如果 $dfn_u = low_u$ ，则该节点 $u$ 与搜索的节点构成一个 SCC。

问题就在于如何快速的求出被节点 $u$ 所更新的其他节点，也就是由 $u$ 构成的 SCC 的剩余节点。

由于 dfs 的本质是一个栈，我们可以维护一个栈用来记录更新的节点信息，直到回溯到 $u$ 时，从栈顶到 $u$ 的所有节点便是这个 SCC 的所有节点。

对于当前节点 $u$ 和遍历节点 $v$ ，模拟方式如下：

如果 $v$ 未被访问：对 $v$ 进行深度有些搜索，同时将回溯后的 $low_v$ 来更新 $low_u$ 。
如果 $v$ 被访问过，且没有出栈：说明 $v$ 当且不属于任何一个 SCC，直接用 $dfn_v$ 更新 $low_u$ 。
如果 $v$ 被访问且不在栈中：说明 $v$ 所在的 SCC 已经被处理，忽略。

模板代码

初始化

int n, m;    // 存图用的边数
int h[N], e[M], ne[M], idx;    // 链式前向星
int dfn[N], low[N], timestamp;    // timestamp 表示时间戳
int stk[N], top;    // 数组模拟栈
bool in_stk[N];        // 判断当前节点是否在栈中
int id[N], scc_cnt;    // 每个节点属于 SCC 分量的编号，SCC 的总数

核心代码

void tarjan(int ver)
{
    dfn[ver] = low[ver] = ++ timestamp;		// 更新时间戳，同时标记节点
    stk[++ top] = ver, in_stk[ver] = true;	// 加入栈中
    
    for (int i = h[ver]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])						// 如果没有被访问过
        {
            tarjan(j);
            low[ver] = min(low[ver], low[j]);
        }
        else if (in_stk[j])
            low[ver] = min(low[ver], dfn[j]);
            // low[ver] = min(low[ver], low[j]);
    }
    
    if (dfn[ver] == low[ver])				// 如果当前节点为 SCC 根节点
    {
        ++ scc_cnt;							// 新增一个 SCC
        int tmp;
        do {
            tmp = stk[top --];
            in_stk[tmp] = false;			// 退栈
            id[tmp] = scc_cnt;				// 更新所属编号
        } while (tmp != ver);				// 根节点同样加进来
    }
}