Tarjan 求强连通分量和缩点

Upd 23.8.29\texttt{Upd 23.8.29} 修正错别字、证明，添加代码和注释

欢迎批评指正！

注意：本文只针对有向图。

前置芝士

  • 什么是强连通分量（SCC）？
    强连通分量，一般指 有向图的极大强连通子图，在这些子图中，所有点双向可达。
  • dfs 序：即 dfs 过程中访问点的顺序。
  • dfs 生成树：由 dfs 过程中访问的边组成的边集 和 原图的点集 组成的树。
  • 树边，非树边：属于 dfs 过程中访问的边 为树边，否则为非树边。

tree edge

  • 返祖边（反向边）：从孩子连接到祖先的边。
  • 前向边：从祖先连接到孩子的边。
  • 横插边：除返祖边和前向边之外的非树边。（连接没有祖孙关系的两点的边。）

edge types

  • 某个强连通分量的根：这个强连通分量重 dfs 序最小的节点。

Tarjan 算法

设两个数组 dfn\mathit{dfn} 和 low\mathit{low}，分别表示 dfs 序和至多通过 11 条非树边所能到达的点的 dfn\mathit{dfn} 的最小值。

看下面这张图：

dfn & low

每个节点的编号就是它的 dfn\mathit{dfn}，旁边标注的数字是 low\mathit{low}，可以自行理解一下。

另外，我们还需要一个栈 stk\mathit{stk} 存节点。

算法流程

Tarjan 是在 dfs 中实现的，每次访问到当前节点 uu，就将它压入 stk\mathit{stk} 中。随后访问所有相邻的点 vv。

  • 如果没访问过，说明 (u,v)(u,v) 是一条树边，继续 dfs。

    dfs vv 的子树结束后，更新 lowu←min⁡(lowu,lowv)\mathit{low}_u\gets\min(\mathit{low}_u,\mathit{low}_v)。因为根据 low\mathit{low} 的定义，走多少条树边都没关系，而 (u,v)(u,v) 是一条树边，我们可以从 uu 走到 vv 后再继续往上爬。也就是说，vv 能到的 lowv\mathit{low}_v，uu 也能到。于是更新。

  • 如果 vv 已被访问过且已属于另一个 SCC，说明 (u,v)(u,v) 是一条横插边，两个 SCC 无关，直接跳过，不予处理。

  • 如果 vv 被访问过且在 stk\mathit{stk} 内，说明 (u,v)(u,v) 是一条返祖边，更新 lowu←min⁡(lowu,dfnv)\mathit{low}_u\gets\min(\mathit{low}_u,\mathit{dfn}_v)。

    因为 low\mathit{low} 的定义为仅通过 11 条非树边，故可以直接走返祖边 (u,v)(u,v)，如果 dfnv\mathit{dfn}_v 比 lowu\mathit{low}_u 小，则更新。

    关于为什么不是 lowu←min⁡(lowu,lowv)\mathit{low}_u\gets\min(\mathit{low}_u,\mathit{low}_v)，因为 lowv\mathit{low}_v 可能已经经过了一条非树边，如果再走返祖边 (u,v)(u,v)，就可能走了两条非树边，与 low\mathit{low} 的定义相悖。（其实这样些也可以得到正确答案，但是求割点时就会错。）

  • 然后判断 uu 是否是根：若 dfnu=lowu\mathit{dfn}_u=\mathit{low}_u，则是当前 SCC 的根，然后退栈到 uu，保存答案。

    因为 dfnu=lowu\mathit{dfn}_u=\mathit{low}_u，所以 uu 的子树内的所有点都不能通过返祖边到达 dfn\mathit{dfn} 比 uu 小的点（否则可以通过树边到达这些子节点，然后走返祖边。使 lowu<dfnu\mathit{low}_u<\mathit{dfn}_u。）

    关于为什么跳出子树至多经过 11 条非树边：如果有 22 条甚至更多，必然有走的最后一条边跳出了子树。那么跳出子树前的点必然在子树内，可以走树边到达，故至多（其实是要且只要）走 11 条非树边。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int n,m;
vector<int> e[11451],stk;// e：边表
int bel[11451];// bel[i] 表示 i 属于哪个 SCC（编号）
vector<vector<int>> scc={{}};// 存每个强连通分量的点的编号
int cnt=1,dfn[11451],low[11451];// cnt：SCC数量（+1）

int dfncnt=1;// 时间戳
void tarjan(int u)
{
	dfn[u]=low[u]=dfncnt++;
	stk.push_back(u);
	for(int v:e[u])// 范围 for，遍历邻居
	{
		if(!dfn[v])// 未访问
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);// 访问并更新
		}
		else if(!bel[v])// in stk
		{
			low[u]=min(low[u],dfn[v]);// 单纯更新
		}
	}
	if(low[u]==dfn[u])// 是当前 SCC 的根
	{
		int t;
		scc.push_back({});
		while(stk.back()!=u)// 退栈到 u
		{
			t=stk.back();
			stk.pop_back();
			scc[cnt].push_back(t);// 保存
			bel[t]=cnt;
		}
		scc[cnt].push_back(u);
		sort(scc[cnt].begin(),scc[cnt].end());
		bel[u]=cnt++;
		stk.pop_back();
	}
}

注意图可能不连通，所以主函数里要加上：

1
2
3
4
5
6
7
for(int i=1;i<=n;i++)
{
	if(!dfn[i])
	{
		tarjan(i);
	}
}

每次都调用一遍 tarjan。

缩点

缩点很好理解，就是将每个强连通分量中的点的信息合并，缩成一个点，形成一个 DAG（有向无环图）。

代码

1
2
3
4
5
6
7
8
9
10
11
for(int i=1;i<=n;i++)
{
	newval[bel[i]]+=val[i];
	for(int j:e[i])
	{
		if(bel[i]!=bel[j])
		{
			newe[bel[i]].push_back(bel[j]);
		}
	}
}

其中 e 为原图，newe 为新图，val 为原图点权（或者什么类似点权的值），newval 为新图点权。

参考

  1. 这位大佬的博客