浅析Tarjan算法&常见应用

强连通分量(Strongly Connected Components)

有向图 强连通分量（SCC）

定义

  • 官方行话版：在有向图$G$中，如果两个顶点$v_i,v_j$间$（v_i>v_j）$有一条从$v_i$到$v_j$的有向路径，同时还有一条从$v_j$到$v_i$的有向路径，则称两个顶点强连通(strongly connected)，如果有向图$G$的每两个顶点都强连通，称$G$是一个强连通图，有向图的极大强连通子图，称为强连通分量(strongly connected components)

  • 浅显易懂版：指有向图中一个最大的子图，满足这个子图中任何两个点都能互相到达

参考blog：

上面三个$blog$写得异常清晰易懂，让我受益匪浅，本来不想再废话了的，但还是想写几个注意事项和易混淆的地方，下面先呈上$Tarjan$的板子（由于$Kosaraju$算法没$Tarjan$好用，我就不放板子了），向发明该算法的$Robert Tarjan（美国计算机科学家）$致敬

Tarjan SCC模板

模板题

注意事项：

  • Tarjan求SCC需要开栈记录元素，再开一个vis数组标记元素是否在栈中

  • 其中color数组标记每个点属于第几个SCC

  • 与求割点不同的地方：

    low[u]=min(low[u],dfn[v])需要v在栈中才执行

    不需要记录父亲节点

  • 与求割点相同的地方：

    都需要（务必）遍历每个点，因为图不一定连通

    新找到一个点都必须执行low[u]=min(low[u],low[v])

    dfn和low数组都是必须要有的，这是算法的核心

code 
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
void tarjan(int u){
    vis[sta[++top]=u]=1; //初始标记入栈
    low[u]=dfn[u]=++deep; //记录dfn和low的序号
    for(int i=head[u];~i;i=e[i].next){ //遍历所有出边
        int v=e[i].v;
        if(!dfn[v]){ //如果没遍历过这个点
            tarjan(v); //就递归遍历下去
            low[u]=min(low[u],low[v]); //low取u和他儿子的较小值
        //如果遍历过且在栈中，low[u]取low[u]和dfn[v]的较小值
        }else if(vis[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){ //如果dfn和low一样了，说明产生了一个SCC
        vis[u]=0; //u标记不在栈中
        color[u]=++num; //标记u属于第num个SCC
        while(sta[top]!=u){ //弹栈顶元素直到弹到u
            color[sta[top]]=num; //所有弹出元素都属于u所在的SCC内
            vis[sta[top--]]=0; //所有弹出元素都标记不在栈中
        }
        top--; //最后需要把u弹出
    }
}

int main(){
    for(int i=1;i<=n;i++){
        if(!dfn[i]) //遍历到所有点（有可能不是连通图）
            tarjan(i);
	}
}

有向图 Tarjan缩点

思想就是因为强连通分量中的每两个点都是强连通的，可以将一个强连通分量当做一个超级点，而点权按题意来定

例题1. 受欢迎的牛（Tarjan缩点记录SCC内节点个数）

code 
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
struct Edge{
	int v,next;
}e[50005];
int cnt,head[10005];
inline void addedge(int u,int v){
	e[cnt]=Edge{v,head[u]};
	head[u]=cnt++; 
}
int n,m,num,deep,top,sta[10005],low[10005],dfn[10005],vis[10005],color[10005];
int Size[10005],chu[50005],ccnt,ans;
inline void tarjan(int u){
	vis[sta[++top]=u]=1;
	low[u]=dfn[u]=++deep;
	for(int i=head[u];~i;i=e[i].next){
		int v=e[i].v;
		if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
		else if(vis[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		vis[u]=0;
		color[u]=++num;
		while(sta[top]!=u){
			vis[sta[top]]=0;
			color[sta[top--]]=num;
		}
		top--;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	memset(head,-1,sizeof(head));
	int u,v;
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u,&v);
		addedge(u,v);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]) tarjan(i);
	}
	for(int i=1;i<=n;i++){
		Size[color[i]]++;
		for(int j=head[i];~j;j=e[j].next){
			int v=e[j].v;
			if(color[v]!=color[i]) chu[color[i]]++;
		}
	}
	for(int i=1;i<=num;i++){
		if(chu[i]==0) ccnt++,ans=Size[i];
	}
	printf("%d\n",ccnt==1?ans:0);
	return 0;
}

例题2. 【模板】缩点（Tarjan缩点+拓扑排序+记忆化搜索dp）

code 
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<cstdio>
#include<cmath>
#include<queue>
#include<iostream>
#include<cstring>
using namespace std;

struct Edge{
	int v,next;
}e[100005],ee[100005];

int cnt,ccnt,hhead[10005],head[10005];

inline void addedge(int u,int v){
	e[cnt]=Edge{v,head[u]};
	head[u]=cnt++; 
}

inline void aaddedge(int u,int v){
	ee[ccnt]=Edge{v,hhead[u]};
	hhead[u]=ccnt++;
}
int n,m,num,deep,top,sta[10005],low[10005],dfn[10005],vis[10005],color[10005];
int val[10005],vval[10005];

inline void tarjan(int u){
	vis[sta[++top]=u]=1;
	low[u]=dfn[u]=++deep;
	for(int i=head[u];~i;i=e[i].next){
		int v=e[i].v;
		if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
		else if(vis[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		vis[u]=0;
		color[u]=++num;
		vval[num]+=val[u];
		while(sta[top]!=u){
			vis[sta[top]]=0;
			vval[num]+=val[sta[top]];
			color[sta[top--]]=num;
		}
		top--;
	}
}

int indeg[10005],tpx[10005],tp;

inline void toposort(){
	queue<int> q;
	for(int i=1;i<=n;i++){
		if(indeg[i]==0){
			q.push(i);
		}
	}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		tpx[++tp]=u;
		for(int i=hhead[u];~i;i=ee[i].next){
			int v=ee[i].v;
			if(indeg[v]){
				indeg[v]--;
				if(indeg[v]==0){
					q.push(v);
				}
			}
		}
	}
}

int dp[10005],ans;
bool vvis[10005];

void dfs(int x){
	dp[x]=vval[x];
	int temp=0;
	for(int i=hhead[x];~i;i=ee[i].next){
		int v=ee[i].v;
		if(!vvis[v]) vvis[v]=1,dfs(v);
		temp=max(temp,dp[v]);
	}
	dp[x]+=temp;
}

int main(){
	scanf("%d%d",&n,&m);
	memset(head,-1,sizeof(head));
	memset(hhead,-1,sizeof(hhead));
	for(int i=1;i<=n;++i) scanf("%d",&val[i]);
	for(int i=1;i<=m;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		addedge(u,v);
	}
	for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
	for(int u=1;u<=n;++u){
		for(int i=head[u];~i;i=e[i].next){
			int v=e[i].v;
			if(color[u]!=color[v]){
				aaddedge(color[u],color[v]);
				indeg[color[v]]++;
			}
		}
	}
	toposort();
	for(int i=1;i<=num;++i){
		int now=tpx[i];
		if(!vvis[now]){
			dfs(now);
			ans=max(ans,dp[now]);
		}
	}
	printf("%d\n",ans);
	return 0;
}

无向图 割点（割顶）与 点双连通分量（V-DCC）

参考blog：

定义

割点：

官方行话版（已经足够易懂了）：在一个无向图中，如果有一个顶点集合，删除这个顶点集合以及这个集合中所有顶点相关联的边以后，图的连通分量增多，就称这个点集为割点集合

易懂人话版：这个点维持着双连通的继续，去掉这个点，这个连通分量就无法再维持下去，分成好几个连通分量

点双连通分量：一个极大子图，删掉其中任意一个点，图仍连通

算法

讲一下核心部分吧，还是Tarjan算法的架构，我们可以把回溯过程遇到的点分为两类

  1. 回溯到的点就是当前父节点：此时只需要判断自己有多少棵子树，如果超过1棵那么这个点就一定是割点（至少一定能把子树分成两半）
  2. 回溯到的点不是父节点：稍微麻烦一点，需要判一下是否有low[v]>=dfv[u]，如果成立的话说明v没办法与他父亲u之前的点连成SCC，那么u就肯定是个割点（至少能把v作父亲的这棵子树给断开）

除此之外，每次从一个节点产生一棵搜索树都需要先开一个child记录这个节点能有多少棵子树

至于点双，最简单的做法：只需要求出割点之后，遍历去掉每一个割点的情况，找连通分量就行了，看题目要求啦

Tarjan 割点模板

code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void tarjan(int u,int fa){
    low[u]=dfn[u]=++deep;
    int child=0;
    for(int i=head[u];~i;i=e[i].next){
        int v=e[i].v;
        if(!dfn[v]){
            tarjan(v,fa);//注意永远都是fa
            low[u]=min(low[u],low[v]);
            if(u!=fa&&low[v]>=dfn[u])//判不是父节点的节点属于割点
                cut[u]=1;
           	if(u==fa)//如果连到了父亲说明多了一个儿子
                child++;
        }
        low[u]=min(low[u],dfn[v]);//务必别忘了这一步
    }
   	if(u==fa&&child>=2)//如果回到父亲了且儿子数多于1就是割点
        cut[u]=1;
}
int main(){
	for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,i)
}

例题 POJ 1523 SPF（求每个割点把图分成的点双数量）

code 
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstring>
using namespace std;
struct Edge{
	int v,next;
}e[50005];

int cnt,head[2005];

inline void addedge(int u,int v){
	e[cnt]=Edge{v,head[u]};
	head[u]=cnt++;
}

int dfn[2005],low[2005],cut[2005],deep;

void tarjan(int u,int fa){
	low[u]=dfn[u]=++deep;
	int child=0;
	for(int i=head[u];~i;i=e[i].next){
		int v=e[i].v;
		if(!dfn[v]){
			tarjan(v,fa);
			low[u]=min(low[u],low[v]);
			if(u!=fa&&low[v]>=dfn[u]) cut[u]=1;
			if(u==fa) child++;
		}
		low[u]=min(low[u],dfn[v]);
	}
	if(u==fa&&child>1) cut[u]=1;
}

int n,u,v,Cnt,ge[2005],color[2005];

inline void init(){
	n=Cnt=cnt=deep=0;
	memset(head,-1,sizeof(head));
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(cut,0,sizeof(cut));
	memset(ge,0,sizeof(ge));
}

void dfs(int x,int gg,int ID){
	for(int i=head[x];~i;i=e[i].next){
		int v=e[i].v;
		if(v!=gg&&color[v]==-1){
			color[v]=ID;
			dfs(v,gg,ID);
		}
	}
}



int main(){
	ios::sync_with_stdio(false);
	init();
	int t=0;
	bool f=false;
	while(cin>>u){
		if(u==0&&f==false) break;
		f=true;
		if(u==0){
			++t;
			for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,i);
			Cnt=0;
			for(int i=1;i<=n;i++){
				if(cut[i]) ge[++Cnt]=i;
			}
			printf("Network #%d\n",t);
			if(Cnt==0) printf("  No SPF nodes\n\n");
			else{
				for(int g=1;g<=Cnt;g++){
					memset(color,-1,sizeof(color));
					int CNT=0;
					for(int i=1;i<=n;i++){
						if(i!=ge[g]&&color[i]==-1){
							++CNT;
							color[i]=CNT;
							dfs(i,ge[g],CNT);
						}
					}
					printf("  SPF node %d leaves %d subnets\n",ge[g],CNT);
				}
				printf("\n");
			}
			init();
			f=false;
			continue;
		}
		cin>>v;
		addedge(u,v);
		addedge(v,u);
		n=max(n,max(u,v));
	}
	return 0;
}

无向图 割边（桥）与 边双连通分量（E-DCC）

定义

割边：边版本的割点，即去掉这条边，该图就无法维持连通

边双连通分量：一个极大子图，删掉图中任意一条边之后，图仍连通

算法

  1. 还是Tarjan，而且算法一模一样，可以直接利用有向图的SCC算法给无向图跑一遍（只需要注意判双向边，用异或运算解决即可），然后就知道了每个点属于哪一个边双连通分量，最后只需要遍历节点找割边就行了（割边的两节点属于不同的双连通分量中）

  2. 还有一种方法可以记录哪一条边是桥：只需要在Tarjan过程中判一下是否有low[v]>dfn[u]，如果存在，则(u,v)这条边是桥（存双向边，要标记两条，异或搞定），除此之外，还需要另外判一下v是不是当前DFS树的根（如果要判重边，则记录一下儿子个数即可，儿子至多为1个才没有重边），如果是，就要跳过（即这条边不是桥）

Tarjan 无向图割边模板（求出边双同时标记割边）

code 
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
void tarjan(int u,int fa){ //这是传入的还是父节点
    vis[sta[++top]=u]=1;
    low[u]=dfn[u]=++deep;
    int precnt=0; //记录一下父节点的儿子个数，用来判重边
    for(int i=head[u];~i;i=e[i].next){
        int v=e[i].v;
        if(v==fa&&precnt==0){//理论上只需要v!=fa即可判双向边
            precnt++;//但如果判重边就需要这个
            continue;
        }
        if(!dfn[v]){
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            //下面这段标记割边（可不写）
            if(low[v]>dfn[u]){ //判是否是桥
                e[i].cut=1;
                e[i^1].cut=1; //双向边
            }
        }else if(vis[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){ //记录每个点属于的边双
        vis[u]=0;
        color[u]=++num;
        while(sta[top]!=u){
            vis[sta[top]]=0;
            color[sta[top--]]=num;
        }
        top--;
    }
}

例题 POJ 3177 Redundant Path（边双+缩点）

code 
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;

struct Edge{
	int v,next;
}e[500005];

int cnt,head[100005];

inline void addedge(int u,int v){
	e[cnt]=Edge{v,head[u]};
	head[u]=cnt++; 
}

int n,m,num,deep,top,sta[100005],low[100005],dfn[100005],vis[100005],color[100005];

inline void tarjan(int u,int fa){
	vis[sta[++top]=u]=1;
	low[u]=dfn[u]=++deep;
	for(int i=head[u];~i;i=e[i].next){
		int v=e[i].v;
		if(i==(fa^1)) continue;
		if(!dfn[v]) tarjan(v,i),low[u]=min(low[u],low[v]);
		else if(vis[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		vis[u]=0;
		color[u]=++num;
		while(sta[top]!=u){
			vis[sta[top]]=0;
			color[sta[top--]]=num;
		}
		top--;
	}
}

int indeg[100005],ans;

inline void init(){
	cnt=ans=deep=num=top=0;
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(head,-1,sizeof(head));
	memset(indeg,0,sizeof(indeg));
	memset(sta,0,sizeof(sta));
	memset(vis,0,sizeof(vis));
	memset(color,0,sizeof(color));
}

int main(){
	while(~scanf("%d%d",&n,&m)){
		init();
		int u,v;
		for(int i=1;i<=m;++i){
			scanf("%d%d",&u,&v);
			addedge(u,v);
			addedge(v,u);
		}
		tarjan(1,-1);
		for(int i=1;i<=n;i++){
			for(int j=head[i];~j;j=e[j].next){
				int v=e[j].v;
				if(color[i]!=color[v]){
					indeg[color[v]]++;
				}
			}
		}
		for(int i=1;i<=num;i++)
			if(indeg[i]==1)
				ans++;
		printf("%d\n",(ans+1)/2); 
	}
	return 0;
}

总结

  • 有向图的的Tarjan算法最为核心
  • 无向图的边双连通分量就是在有向图SCC基础上判一下双向边（满足v!=fa即可），而割边的标记需要另外加一句low[v]>dfn[u]的判断
  • 无向图的割点比较特殊，需要判两种回溯点的情况，同时还要记录儿子个数，并且递归传递的父节点永远不变，而点双连通分量的求取只需要先求割点再去除割点遍历就行了，比较灵活
算法
图论 数据结构 割点 SCC

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！