强连通分量Tarjan算法学习笔记-526互联

定义

一个有向图 \(G\) 强连通，指的是 \(G\) 的任意两个结点连通。强连通分量 SCC 指的是极大的强连通子图。

Tarjan 的做法

首先来看一个 DFS 树，图源 OI Wiki

其中所有的边都是原有向图的边。从 \(1\) 号节点开始跑 DFS ，我们把这些边分为两类：

树边，也就是图中黑色的边，构成了 DFS 树本树；
返祖边，也就是图中红色的边，返祖边的出现可能会带来环；
横叉边，也就是图中红色的边，在 DFS 树中，在同一层之间连接点的边即为横叉边；
前向边，也就是途中绿色的边，在 DFS 树种主打一个“跳级”操作。

那么，你可以思考到，如果节点 \(u\) 是某个强连通分量在搜索树种遇到的第一个节点，那么其余结点一定在以 \(u\) 为根的子树中。

反证法：假设有个结点 \(v\) 在该强连通分量中但是不在以 \(u\) 为根的子树中，那么 \(u\) 到 \(v\) 的路径中肯定有一条离开子树的边。但是这样的边只可能是横叉边或者反祖边，然而这两条边都要求指向的结点已经被访问过了，这就和 \(u\) 是第一个访问的结点矛盾了。得证。

Tarjan 还另外对每个维护了两个变量：

\(\operatorname{dfn}(u)\)：深度优先搜索时，结点 \(u\) 被搜到的次序；
\(\operatorname{low}(u)\)：从 \(u\) 开始搜索，能搜索到的深度最低的结点 —— 显然，如果 \(u\) 上有一个返祖边，肯定是跟着返祖边往上跑；再就是寄希望于自己的孩子能有一个返祖边往回跑，否则就只能是他自身。

一个结点的子树内结点的 \(\operatorname{dfn}\) 都大于该结点的 \(\operatorname{dfn}\)。

并且可以观察到：从根开始的一条路径上的 \(\operatorname{dfn}\) 严格递增，\(\operatorname{low}\) 严格非降。

那么接下来就是 Tarjan 算法的流程：
按照深度优先搜索的顺序对所有的结点进行搜索，维护每个节点的 \(\operatorname{dfn}\) 和 \(\operatorname{low}\) ，并让这个结点入栈。
在搜索过程中，对于 \(u\) 与其相邻的非父结点 \(v\) ，只可能有以下三种情况

\(v\) 未被访问过。继续对 \(v\) 进行 DFS ，在回溯的过程中用 \(\operatorname{low}(v)\) 更新 \(\operatorname{low}(u)\) 。理由是：如果 \(v\) 能回到比 \(u\) 更早的结点，那 \(u\) 一定能通过走 \(u\rightarrow v\) 这条路径走到更早的结点；
\(v\) 被访问过，且还在栈中，那么就用 \(\operatorname{dfn}(v)\) 更新 \(\operatorname{low}(u)\) ；
\(v\) 被访问过，已不在栈中：说明 \(v\) 已搜索完毕，其所在连通分量已被处理，所以不用对其做操作。

画图理解如下：

实现如下

void tarjan(int u) {
	low[u] = dfn[u] = ++dfncnt, s[++tp] = u, in_stack[u] = 1;
	for (int i = h[u]; i; i = e[i].nex) {
	    const int &v = e[i].t;
	    if (!dfn[v]) {
			tarjan(v);
	    	low[u] = min(low[u], low[v]);
	    } 
		else if (in_stack[v]) low[u] = min(low[u], dfn[v]); // 回溯 
	}
	if (dfn[u] == low[u]) {
	    ++ sc;
	    while (s[tp] != u) {
	    	scc[s[tp]] = sc;
	    	++ sz[sc];
	    	in_stack[s[tp]] = 0;
	    	--tp;
	    }
	    scc[s[tp]] = sc;
	    ++ sz[sc];
	    in_stack[s[tp]] = 0;
	    -- tp;
	}
}