Tarjan 算法求解无向图的割点与割边

This blog post is only available in Simplified Chinse.

在一幅无向图中，如果删除了一个点，导致图分成了两个或多个联通块（强连通分量），那么这个点就是割点。怎么求这样的点呢？最原始暴力的方法就是每次枚举一个点，删除，跑一遍最短路。今天我们可以用更高级的 Tarjan 算法 $\displaystyle \Theta (N)$ 求解。

割点与割边

割点的定义

在一个无向图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点集合。

也就是前文所述：如果删除了一个点，导致图分成了两个或多个联通块（强连通分量），那么这个点就是割点（也叫作割顶）。说得再通俗点，去掉割点，图会不连通。

割边的定义

与割点类似：

假设有连通图 G，e 是其中一条边，如果 G-e 是不连通的，则边 e 是图 G 的一条割边。

就是说如果把这条边删除，图分为两个强连通分量，这条边就称为割边（也称为桥）。

暴力求解

以割点为例：前面也提到了，最原始的暴力方法：就是每次枚举一个点，删除，跑一遍最短路，看看结点 1 是否还可以到达除了删除点之外的所有点，如果不能则说明删除点是割点。如果跑最稳的 Dijkstra+Heap，复杂度也要 $\Theta (N\ast M \ast log_2(M))$ ……

Tarjan 算法

求解割点和割边，用 Tarjan 算法会十分优秀。在此之前我们要先学习下什么是 DFS 树。

DFS 树

所谓 DFS 树，就是对一幅图进行 DFS 按照 DFS 顺序得到的一棵生成树。可以从任意点开始 DFS（一般从 1 开始），并不影响答案。在这幅图中，在 DFS 树中的边称为树边，不在 DFS 树中的边称为非树边。

返祖边

这里我们只研究无向图。在无向图中，非树边只会以返祖边的形式存在。也就是说非树边会从当前点指向某个祖先。例如下图中，D 指向 A 的边就是返祖边。（这张图其实是无向图，为了便于理解，按照 DFS 的顺序标出方向）

graph TB
	A((A))-->B((B))
	B((B))-->C((C))
	B((B))-->D((D))
	D((D))-->A

算法原理

割点的求解

可以把割点分为两种情况：

根节点在 DFS 树中有多于一个子节点，那么根节点就是割点；
对于非根节点 u，它至少有一棵子树没有返祖边可以到达 u 的祖先。

第一种情况很好理解；对于第二种情况，如果 u 有一个子树中有一个结点 x 有返祖边可以到达 u 的祖先，那么把 u 删除后，由于原来的树是联通的，那么我们找出的 x 仍然有边可以到达 u 以上的所有点，又因为那个点在 u 的一棵子树里，那么这棵子树就可以到达 u 以上的所有点！

割边的求解

割边甚至更加简单，忽略第一种情况，如果一条边是割边，当且仅当其子树均没有跨过这条边。

具体实现

以求割点为例，每个节点维护几个信息：

$dfn(x)$ 表示点 x 的标号，即它是第几个被遍历到的点。维护这一信息十分有用，因为如果点 a 是点 b 的祖先，那么 $dfn(a) \lt dfn(b)$ 。
$low(x)$ 表示 x 点不经过其的父节点，能通过返祖边到达的 $dfn$ 最小的祖先的 $dfn$ 值。初始值为 $dfn(x)$ 。
$fa(x)$ 表示 x 的父节点。在求割边时，我们记录的 $fa(x)$ 表示 x 与其祖先之间的边的标号。

在 DFS 的同时可以维护这几个信息，回溯时判断如果 $low(v)>dfn(x)$ （v 是 x 的儿子）说明 x 是割点。

核心代码如下：

inline void DFS(int x){
	vis[x]=1;dfn[x]=low[x]=++acnt;
	int nowson=0;
	for (int i=lnk[x];i;i=nxt[i]) if (!vis[son[i]]){
		nowson++;
		fa[son[i]]=x;
		DFS(son[i]);
		low[x]=min(low[x],low[son[i]]);
		if (x!=1&&low[son[i]]>dfn[x]) ans[x]=true;
		if (x==1&&nowson>=2) ans[x]=true;
	} else if (son[i]!=fa[x]) low[x]=min(dfn[son[i]],low[x]);
}

例题

割点模板题

POJ1144 Network

割边模板题

ZOJ2588 Burning Bridges

参考代码

割点（POJ1144）

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=105,maxe=1000005;
int n,fa[maxn];
int tot=0,acnt=0,dfn[maxn],low[maxn];
int lnk[maxn],nxt[maxe],son[maxe];
bool vis[maxn],ans[maxn];
inline void add(int x,int y){
	tot++;son[tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;
}
inline void Init(){
	tot=0;acnt=0;
	memset(fa,0,sizeof(fa));
	memset(lnk,0,sizeof(lnk));
	memset(nxt,0,sizeof(nxt));
	memset(son,0,sizeof(son));
	memset(vis,0,sizeof(vis));
	memset(dfn,0,sizeof(dfn));
	memset(ans,0,sizeof(ans));
}
inline void DFS(int x){
	vis[x]=1;dfn[x]=low[x]=++acnt;
	int nowson=0;
	for (int i=lnk[x];i;i=nxt[i]) if (!vis[son[i]]){
		nowson++;
		fa[son[i]]=x;
		DFS(son[i]);
		low[x]=min(low[x],low[son[i]]);
		if (x!=1&&low[son[i]]>=dfn[x]) ans[x]=true;
		if (x==1&&nowson>=2) ans[x]=true;
	} else if (son[i]!=fa[x]) low[x]=min(dfn[son[i]],low[x]);
}
int main(){
	for (;;){
		scanf("%d",&n);if (n==0) break;
		Init();int ans_cnt=0;
		int x;scanf("%d",&x);
		while (x!=0){
			int now=0;char ch=getchar();
			while (ch!=10&&ch!=13){
				while ((ch<'0'||ch>'9')&&ch!=10&&ch!=13) ch=getchar();
				if (ch==10||ch==13) break;
				while (ch>='0'&&ch<='9') now=now*10+ch-'0',ch=getchar();
				add(x,now);add(now,x);
				now=0;
			}
			scanf("%d",&x);
		}
		DFS(1);
		for (int i=1;i<=n;i++) ans_cnt+=ans[i];
		printf("%d\n",ans_cnt);
	}
	return 0;
}

割边（ZOJ2588）

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
const int maxn=10005,maxe=200005;
int T,n,m,fa[maxn];
int tot=0,acnt=0,dfn[maxn],low[maxn];
int lnk[maxn],nxt[maxe],son[maxe],id[maxe];
bool vise[maxe],ans[maxe],vis[maxn];
vector<int> que_ans;
inline void add(int x,int y,int z){
	tot++;son[tot]=y;id[tot]=z;nxt[tot]=lnk[x];lnk[x]=tot;
}
inline void Init(){
	tot=0;acnt=0;que_ans.clear();
	memset(fa,0,sizeof(fa));
	memset(id,0,sizeof(id));
	memset(lnk,0,sizeof(lnk));
	memset(nxt,0,sizeof(nxt));
	memset(son,0,sizeof(son));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(ans,1,sizeof(ans));
	memset(vis,0,sizeof(vis));
}
inline void DFS(int x){
	dfn[x]=low[x]=++acnt;
	for (int i=lnk[x];i;i=nxt[i]) if (!vis[son[i]]){
		fa[son[i]]=id[i];vis[son[i]]=true;
		DFS(son[i]);
		if (low[son[i]]<=dfn[x]) ans[id[i]]=false;
		low[x]=min(low[x],low[son[i]]);
	} else if (id[i]!=fa[x]) low[x]=min(dfn[son[i]],low[x]),ans[id[i]]=false;
}
int main(){
	scanf("%d",&T);
	while (T--){
		scanf("%d%d",&n,&m);
		Init();
		for (int i=1;i<=m;i++){
			int x,y;scanf("%d%d",&x,&y);
			add(x,y,i);add(y,x,i);
		}
		vis[1]=true;DFS(1);
		
		for (int i=1;i<=m;i++) if (ans[i]) que_ans.push_back(i);
		int nn=que_ans.size();printf("%d\n",nn);
		for (int i=0;i<nn-1;i++) printf("%d ",que_ans[i]);
		if (nn!=0) printf("%d\n",que_ans[nn-1]);
		// printf("LOW: ");for (int i=1;i<=n;i++) printf("%d ",low[i]);printf("\n");
		// printf("DFN: ");for (int i=1;i<=n;i++) printf("%d ",dfn[i]);printf("\n");
		if (T>0) printf("\n");
	}
	return 0;
}

参考

割点_百度百科割边_百度百科

吐槽一下，POJ1144 调代码一直调不对，然后去 discuss 区搞了组数据，用 Mermaid 生成图，我以为会很清晰，结果是这样的……

graph TB;
17---4
17---18
1---11
7---5
13---1
3---1
14---5
15---20
9---12
6---8
16---14
18---8
8---4
20---18
20---10
2---3
12---5
5---9
5---20
19---20
19---9
19---11
19---2
11---3
4---15
10---3
21---3

吐血……

8/5/2018