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 点不经过其的父节点，能通过返祖边到达的最小的祖先的值。初始值为。

在 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));
}
  {
	vis[x]=;dfn[x]=low[x]=++acnt;
	 nowson=;
	 ( i=lnk[x];i;i=nxt[i])  (!vis[son[i]]){
		nowson++;
		fa[son[i]]=x;
		(son[i]);
		low[x]=(low[x],low[son[i]]);
		 (x!=&&low[son[i]]>=dfn[x]) ans[x]=;
		 (x==&&nowson>=) ans[x]=;
	}   (son[i]!=fa[x]) low[x]=(dfn[son[i]],low[x]);
}
{
	 (;;){
		(,&n); (n==) ;
		(); ans_cnt=;
		 x;(,&x);
		 (x!=){
			 now=; ch=();
			 (ch!=&&ch!=){
				 ((ch<||ch>)&&ch!=&&ch!=) ch=();
				 (ch==||ch==) ;
				 (ch>=&&ch<=) now=now*+ch-,ch=();
				(x,now);(now,x);
				now=;
			}
			(,&x);
		}
		();
		 ( i=;i<=n;i++) ans_cnt+=ans[i];
		(,ans_cnt);
	}
	 ;
}

割边（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));
	(dfn,,(dfn));
	(low,,(low));
	(ans,,(ans));
	(vis,,(vis));
}
{
	dfn[x]=low[x]=++acnt;
	 ( i=lnk[x];i;i=nxt[i])  (!vis[son[i]]){
		fa[son[i]]=id[i];vis[son[i]]=;
		(son[i]);
		 (low[son[i]]<=dfn[x]) ans[id[i]]=;
		low[x]=(low[x],low[son[i]]);
	}   (id[i]!=fa[x]) low[x]=(dfn[son[i]],low[x]),ans[id[i]]=;
}
{
	(,&T);
	 (T--){
		(,&n,&m);
		();
		 ( i=;i<=m;i++){
			 x,y;(,&x,&y);
			(x,y,i);(y,x,i);
		}
		vis[]=;();
		
		 ( i=;i<=m;i++)  (ans[i]) que_ans.(i);
		 nn=que_ans.();(,nn);
		 ( i=;i<nn;i++) (,que_ans[i]);
		 (nn!=) (,que_ans[nn]);
		
		
		 (T>) ();
	}
	 ;
}

参考

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

吐槽一下，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