Tarjan-图的连通性

发表于 更新于 分类于 ， ， 本文字数： 7.6k 阅读时长 ≈ 7 分钟

强连通分量

poj 2186 Popular Cows

Task

给定一个有n头牛的牛群，和m个有序对（A，B）。（A，B）表示牛A认为牛B是红人，且如果牛B认为牛C是红人，那么牛A也认为牛C是红人，求被所有牛认为是红人的牛的总数。
$1<=n<=10000$
$1<=m<=50000$
$1<=A,B<=N$

Solution

首先这可以构成一幅有向图。然后由传递性可知，如果两只牛相互认为对方是红人，那么认为它们是红人的牛和它们认为是红人的牛都是一样的，那么我们就可以把它们缩成一个点。而只有在一个强连通分量中的牛才会且一定会互相认为对方是红人，所以我们可以用Tarjan进行强连通分量分解，并缩点，得到一个DAG。在这个DAG中我们由拓扑序得最后没有出边的点就是答案，但由于图不一定连通，所以还需要判断一下。

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
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <string.h>
#define N 50005
#define M 10005
using namespace std;
vector<int>E[M];
struct kxj{
	int t,nxt;
}edge[N<<1];
int n,ans,head[M],tot,cnt[M],Q[M],sz[M],dergee[M];
int dfn[M],low[M],allc,stk[M],top,belong[M],sccid;
void Add(int a,int b){
	edge[tot]=(kxj){b,head[a]};head[a]=tot++;
}
void Tarjan(int x){
	dfn[x]=low[x]=++allc;
	stk[++top]=x;
	for(int i=head[x];~i;i=edge[i].nxt){
		int y=edge[i].t;
		if(!dfn[y]){
			Tarjan(y);
			low[x]=min(low[y],low[x]);
		}else if(!belong[y])low[x]=min(low[x],dfn[y]);
	}
	if(low[x]==dfn[x]){
		++sccid;
		while(top){
			int t=stk[top--];
			belong[t]=sccid;
			sz[sccid]++;
			if(x==t)break;
		}
	}
}
void solve(){
	int L=0,R=0;
	for(int i=1;i<=sccid;i++){
		if(dergee[i]==0)Q[R++]=i;
		cnt[i]=sz[i];
	}
	while(L<R){
		int x=Q[L++];
		if(cnt[x]==n)ans+=sz[x];
		for(int i=0;i<E[x].size();i++){
			int y=E[x][i];
			cnt[y]+=cnt[x];
			if(--dergee[y]==0)Q[R++]=y;
		}
	}
}
int main(){
	memset(head,-1,sizeof(head));
	int m,a,b;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d %d",&a,&b);
		Add(a,b);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])Tarjan(i);
	for(int i=1;i<=n;i++){
		int x=belong[i];
		for(int j=head[i];~j;j=edge[j].nxt){
			int y=belong[edge[j].t];
			if(y==x)continue;
			dergee[y]++;
			E[x].push_back(y);
		}
	}
	solve();
	printf("%d\n",ans);
	return 0;
}

边双连通分量

poj 3352 Road Construction

Task

给定一张n点m边的无向图，求最少在加几条边使其不存在桥。
$1<=n<=1000$
$1<=m<=1000$

Solution

我们用Tarjan先将图缩成一棵树，然后答案就是得到的数的叶子节点的个数除以2向上取整。

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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#define M 1005
using namespace std;
struct kxj{
	int t,nxt;
}edge[M+M];
int dfn[M],low[M],tot,head[M],setID,stk[M],top,belong[M],bccid,son[M];
void Add(int a,int b){
	edge[tot]=(kxj){b,head[a]};head[a]=tot++;
	edge[tot]=(kxj){a,head[b]};head[b]=tot++;
}
void Tarjan(int x,int id){
	dfn[x]=low[x]=setID++;
	stk[++top]=x;
	for(int i=head[x];~i;i=edge[i].nxt){
		int y=edge[i].t;
		if(i==id)continue;
		if(!dfn[y]){
			Tarjan(y,i^1);
			low[x]=min(low[x],low[y]);
		}else low[x]=min(low[x],dfn[y]);
	}
	if(low[x]==dfn[x]){
		++bccid;
		while(top){
			int t=stk[top--];
			belong[t]=bccid;
			if(t==x)break;
		}
	}
}
int main(){
	memset(head,-1,sizeof(head));
	int n,m,a,b,ans=0;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d %d",&a,&b);
		Add(a,b);
	}
	Tarjan(1,-1);
	for(int i=1;i<=n;i++){
		int x=belong[i];
		for(int j=head[i];~j;j=edge[j].nxt)
			if(x!=belong[edge[j].t])son[x]++;
	}
	for(int i=1;i<=bccid;i++)ans+=son[i]==1;
	printf("%d\n",(ans+1)/2);
	return 0;
}

点双连通分量

bzoj 2730 矿场搭建

Task

煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。(by bzoj)
$n<=500$

Solution

此题我们画出图之后可以发现非割点（割顶）的点坍塌后对结果并无影响，所以我们只用考虑割点坍塌的情况。如果一个点双连通分量中两个割点，那么我们无需在此点双连通分量中加入救生井，因为一个割点坍塌，可以从另一个割点离开。
如果一个点双中只有一个割点，那么我们就必须在此放一个救生井。如果一个连通块中只有一个点双，那么此点双中将无割点，所以我们要在此点双中放两个救生井，因为一个救生井坍塌后还可以从另一个逃生。

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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <iostream>
#include <algorithm>
#define M 505
using namespace std;
struct kxj{
	int t,nxt;
}edge[M<<1];
int ans1,head[M],tot,dfn[M],low[M],setID;
int isCut[M],root,bccid,belong[M],stk[M],top;
vector<int>Bcc[M];
long long ans2;
void Add(int a,int b){
	edge[tot]=(kxj){b,head[a]};head[a]=tot++;
	edge[tot]=(kxj){a,head[b]};head[b]=tot++;
}
void BCC(int x){
	bccid++;
	while(top){
		int t=stk[top--];
		int a=edge[t].t,b=edge[t^1].t;
		if(belong[a]!=bccid){
			belong[a]=bccid;
			Bcc[bccid].push_back(a);
		}
		if(belong[b]!=bccid){
			belong[b]=bccid;
			Bcc[bccid].push_back(b);
		}
		if(t==x)break;
	}
}
void Tarjan(int x,int eid){
	int child=0,flag=0;
	dfn[x]=low[x]=++setID;
	for(int i=head[x];~i;i=edge[i].nxt){
		int y=edge[i].t;
		if(!dfn[y]){
			stk[++top]=i;
			Tarjan(y,i^1);
			low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x]){
				child++;flag=1;
				BCC(i);
			}
	
		}else if(eid!=i)low[x]=min(low[x],dfn[y]);
	}
	if(root!=x&&flag)isCut[x]=1;
	if(root==x&&child>1)isCut[x]=1;
}				
int main(){
	int n,a,b,m,o=0;
	while(~scanf("%d",&n)){
		if(!n)return 0;
		ans2=1;m=tot=top=setID=ans1=bccid=0;
		memset(head,-1,sizeof(head));
		memset(dfn,0,sizeof(dfn));
		memset(low,0,sizeof(low));
		memset(isCut,0,sizeof(isCut));
		memset(belong,0,sizeof(belong));
		for(int i=1;i<=n;i++){
			scanf("%d %d",&a,&b);
			Add(a,b);m=max(m,max(a,b));
		}
		for(int i=1;i<=m;i++)
			if(!dfn[i])root=i,Tarjan(i,-1);
		for(int i=1;i<=bccid;i++){
			int cnt=0,res=Bcc[i].size();
			for(int j=0;j<res;j++){
				if(isCut[Bcc[i][j]])cnt++;
			}
			if(cnt==0)ans2*=res*(res-1)/2,ans1+=2;
			if(cnt==1)ans2*=res-1,ans1++;
			Bcc[i].clear();
		}
		cout<<"Case "<<++o<<": "<<ans1<<" "<<ans2<<endl;
	}
}

点入栈：

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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <iostream>
#include <algorithm>
#define M 505
using namespace std;
struct kxj{
	int t,nxt;
}edge[M<<1];
int ans1,head[M],tot,dfn[M],low[M],setID;
int isCut[M],root,bccid,belong[M],stk[M],top;
vector<int>Bcc[M];
long long ans2;
void Add(int a,int b){
	edge[tot]=(kxj){b,head[a]};head[a]=tot++;
	edge[tot]=(kxj){a,head[b]};head[b]=tot++;
}
void BCC(int x){
}
void Tarjan(int x,int eid){
	int child=0,flag=0;
	dfn[x]=low[x]=++setID;
	stk[++top]=x;
	for(int i=head[x];~i;i=edge[i].nxt){
		int y=edge[i].t;
		if(!dfn[y]){
			Tarjan(y,i^1);
			low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x]){
				child++;bccid++;
				isCut[x]=1;
				while(top){
					int t=stk[top--];
					Bcc[bccid].push_back(t);
					if(t==y)break;
				}
				Bcc[bccid].push_back(x);
			}
		}
		else if(eid!=i)low[x]=min(low[x],dfn[y]);
	}
	if(root==x&&child<=1)isCut[x]=0;
}				
int main(){
	int n,a,b,m,o=0;
	while(~scanf("%d",&n)){
		if(!n)return 0;
		ans2=1;m=tot=top=setID=ans1=bccid=0;
		memset(head,-1,sizeof(head));
		memset(dfn,0,sizeof(dfn));
		memset(low,0,sizeof(low));
		memset(isCut,0,sizeof(isCut));
		memset(belong,0,sizeof(belong));
		for(int i=1;i<=n;i++){
			scanf("%d %d",&a,&b);
			Add(a,b);m=max(m,max(a,b));
		}
		for(int i=1;i<=m;i++)
			if(!dfn[i])root=i,Tarjan(i,-1);
		for(int i=1;i<=bccid;i++){
			int cnt=0,res=Bcc[i].size();
			for(int j=0;j<res;j++){
				if(isCut[Bcc[i][j]])cnt++;
			}
			if(cnt==0)ans2*=res*(res-1)/2,ans1+=2;
			if(cnt==1)ans2*=res-1,ans1++;
			Bcc[i].clear();
		}
		cout<<"Case "<<++o<<": "<<ans1<<" "<<ans2<<endl;
	}
}