图的连通性相关问题

发表于 | 分类于 | 阅读次数:

##无向图
###概念
对于无向图来说，两点的连通的特殊情况有两种：点双连通、边双连通。

我们先引入割点和割桥的概念：

  • 割点：删去此点后图不连通；
  • 割边：删去此边后图不连通。

那么双连通关系就很好解释了：

  • 点双连通：两点之间的路径不存在割点；
  • 边双连通：两点之间的路径不存在割桥。

然而只是知道两点的关系并无大用，我们常常需要知道一些点集的关系：

  • 点双连通分量（Bi-connected Component, bcc）：任意两点都双连通的极大点集。割点可能属于多个点双连通分量，但一条边只属于一个。
  • 边双连通分量（Edge Bi-connected Component, ebc）：任意两点都双连通的极大点集。

求法

首先明确求解图的连通性问题的基本方法：以 DFS 为基础，纪录每个点的 DFS 顺序 dfn 和这个点在 DFS 树中后代的 DFS序最小值 low 。

我们先考虑割点、割边的求法，割点的话只要保证后代节点与前代节点没有连边，且此节点不是树根；如若割点只有一个后代，则割点和后代的连边就是割边。

求出割点割边之后，双连通分量就好求了：

  • 对于边双连通分量，我们只要保证其中没有割边即可，那就以割边为界把总点集分割成多个部分；
  • 而点双不能简单地划分点，应将边入栈，划分边集，然后在算出对应的点集。

BCC:

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>

const int MAXV,MAXE;

struct E{int next,fr,to;} e[MAXE];int ecnt,G[MAXV];
void addEdge(int u,int v){e[++ecnt]=(E){G[u],u,v};G[u]=ecnt;}
void addEdge2(int u,int v){addEdge(u,v);addEdge(v,u);}

int belong[MAXV];std::vetor<int> bcc[MAXV];int bcnt;
std::stack<E> st;
void tarjan(int u,int fa)
{
	low[u]=dfn[u]=++dcnt;
	for(i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(!dfn(v))
		{
			st.push((E){0,u,v});
			dfs(v,u);
			low[u]=std::min(low[u],low[v]);
			if(low[v]>=dfn[u])
			{
				bcnt++;
				E t;
				do
				{
					t=st.top();st.pop();
					if(belong[u]!=bcnt) {bcc[bcnt].push_back(t.u);belong[t]=bcnt;}
					if(belong[v]!=bcnt) {bcc[bcnt].push_bakc(t.v);belong[t]=bcnt;}
				}while(t.u!=u||t.v!=v);
			}
			else if(dfn[v]<dfn[u]&&v!=fa)
			{
				st.push((E){0,u,v});
				low[u]=std::min(low[u],dfn[v]);
			}
		}
	}
}

EBC:

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
#include<iostream>
#include<cstdio>

const int MAXV,MAXE;

struct E{int next,to;} e[MAXE];int ecnt,G[MAXV];
void addEdge(int u,int v){e[++ecnt]=(E){G[u],v};G[u]=ecnt;}
void addEdge2(int u,int v){addEdge(u,v);addEdge(v,u);} 

int low[MAXV],dfn[MAXE],dcnt;
bool isBrg[MAXE];

void tarjan(int u,int fa)
{
	int i;low[u]=dfn[u]=++dcnt;
	for(i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(!dfn[v])
		{
			dfs(v,u);
			low[u]=std::min(low[u],low[v]);
			if(low[v]>=dfn[u]) isBrg[i]=true;
		}else if(dfn[v]<dfn[u]&&v!=fa) low[u]=std::min(low[u],dfn[v]);
	}
}

[LA3523] Knights of the Round Table

有 $n$ 个圆桌骑士，每次圆桌会议至少引诱 $3$ 哥其实参加。且相互憎恨的骑士不能相邻。由于会议需要表决，故参加的人数必须为奇数。现在知道哪些骑士相互憎恨，统计有多少个骑士不可能参加同一会议。

$n\leq1000,m\leq10^6$

其实就是求一无向图内不在一简单奇圈内的点数。

这道题牵扯到无向图中常见的套路：按照点双连通分量是否二分图分类讨论。那么对于这道题，需要用到这样一个结论：如果点双不是二分图，那么它一定包含奇圈，且所有点都在某一及奇圈内。

那么只要找出并统计一下即可。

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>

const int MAXN=1e3+5,MAXM=1e6+5;

int n,m;

bool ban[MAXN][MAXN];
struct E{int next,fr,to;} e[MAXM<<1];int ecnt,G[MAXN];
void addEdge(int u,int v){e[++ecnt]=(E){G[u],u,v};G[u]=ecnt;}
void addEdge2(int u,int v){addEdge(u,v);addEdge(v,u);}

std::vector<int> bcc[MAXN];int bcnt,belong[MAXN];

std::stack<E> st;
int low[MAXN],dfn[MAXN],dcnt;
void tarjan(int u,int la)
{
	low[u]=dfn[u]=++dcnt;
	for(int i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(!dfn[v])
		{
			st.push((E){0,u,v});
			tarjan(v,u);
			low[u]=std::min(low[u],low[v]);
			if(low[v]>=dfn[u])
			{
				bcc[++bcnt].clear();
				E t;
				do
				{
					t=st.top();st.pop();
					if(belong[t.fr]!=bcnt) bcc[bcnt].push_back(t.fr),belong[t.fr]=bcnt;
					if(belong[t.to]!=bcnt) bcc[bcnt].push_back(t.to),belong[t.to]=bcnt;
				}while(t.fr!=u||t.to!=v);
			}
		}else if(dfn[v]<dfn[u]&&v!=la)
		{
			st.push((E){0,u,v});
			low[u]=std::min(low[u],dfn[v]);
		}
	}
}

inline void findBCC()
{
	memset(dfn,0,sizeof(dfn));
	memset(belong,0,sizeof(belong));
	dcnt=bcnt=0;
	for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);
}

int clr[MAXN];

bool judBi(int u,int bid)
{
	for(int i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(belong[v]!=bid) continue;
		if(clr[u]==clr[v]) return false;
		if(clr[v]==-1)
		{
			clr[v]=clr[u]^1;
			if(!judBi(v,bid)) return false;
		}
	}
	return true;
}

bool inOddRing[MAXN];
inline void calOdd()
{
	int i,j;
	memset(inOddRing,false,sizeof(inOddRing));
	for(i=1;i<=bcnt;i++)
	{
		memset(clr,-1,sizeof(clr));
		for(j=0;j<bcc[i].size();j++) belong[bcc[i][j]]=i;
		clr[bcc[i][0]]=0;
		if(!judBi(bcc[i][0],i))
			for(j=0;j<bcc[i].size();j++) inOddRing[bcc[i][j]]=true;
	}
}

int main()
{
	int Case=0;
	while(~scanf("%d%d",&n,&m)&&(n||m))
	{
		memset(ban,false,sizeof(ban));
		memset(G,0,sizeof(G));ecnt=0;
		int i,j;
		for(i=1;i<=m;i++)
		{
			int u,v;scanf("%d%d",&u,&v);
			ban[u][v]=ban[v][u]=true;
		}
		for(i=1;i<n;i++)
			for(j=i+1;j<=n;j++)
				if(!ban[i][j]) addEdge2(i,j);
		findBCC();
		calOdd();
		int ans=0;
		for(i=1;i<=n;i++) if(!inOddRing[i]) ans++;
		printf("%d\n",ans);
	}
	return 0;
}

###[LA5135] Mining Your Own Business [Wolrd Finals2011]

在无向图上选择尽量少的点涂黑，使得任意删除一个点后每个点双连通分量至少有一个黑点。

$n\leq5\times10^4$

把割点涂黑是不划算的，因为万一割点被删去了，直接 GG

在一个点双中一个黑点就够了

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<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<stack>
typedef long long ll;
const int MAXN=1e5+5;

struct E{int next,fr,to;} e[MAXN];int ecnt,G[MAXN];
void addEdge(int u,int v){e[++ecnt]=(E){G[u],u,v};G[u]=ecnt;}
void addEdge2(int u,int v){addEdge(u,v);addEdge(v,u);}

std::vector<int> bcc[MAXN];int bcnt,belong[MAXN];

int low[MAXN],dfn[MAXN],dcnt;
std::stack<E> st;
bool isCut[MAXN];

void tarjan(int u,int la)
{
	int ccnt=0;low[u]=dfn[u]=++dcnt;
	for(int i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(!dfn[v])
		{
			++ccnt;
			st.push((E){0,u,v});
			tarjan(v,u);
			low[u]=std::min(low[u],low[v]);
			if(low[v]>=dfn[u])
			{
				bcc[++bcnt].clear();
				isCut[u]=true;
				E t;
				do
				{
					t=st.top();st.pop();
					if(belong[t.fr]!=bcnt) bcc[bcnt].push_back(t.fr),belong[t.fr]=bcnt;
					if(belong[t.to]!=bcnt) bcc[bcnt].push_back(t.to),belong[t.to]=bcnt;
				}while(u!=t.fr||v!=t.to);
			}	
		}else if(dfn[v]<dfn[u])
		{
			st.push((E){0,u,v});
			low[u]=std::min(low[u],dfn[v]);
		}
	}
	if(la==0&&ccnt==1) isCut[u]=false;
}

int main()
{
	int Case=0,n;
	while(~scanf("%d",&n)&&n)
	{
		memset(G,0,sizeof(G));ecnt=0;
		int i,j;
		for(i=1;i<=n;i++)
		{
			int u,v;scanf("%d%d",&u,&v);
			addEdge2(u,v);
		}
		memset(dfn,0,sizeof(dfn));
		memset(belong,0,sizeof(belong));
		memset(isCut,false,sizeof(isCut));
		bcnt=dcnt=0;
		tarjan(1,0);
		int ans1=0;ll ans2=1;
		for(i=1;i<=bcnt;i++)
		{
			int ccnt=0;
			for(j=0;j<bcc[i].size();j++)
				if(isCut[bcc[i][j]]) ccnt++;
			if(ccnt==1) ans1++,ans2*=(ll)bcc[i].size()-ccnt;
		}
		if(bcnt==1) ans1=2,ans2=bcc[1].size()*(bcc[1].size()-1)/2;
		printf("Case %d: %d %lld\n",++Case,ans1,ans2);
	}
	return 0;
}

##有向图

时间复杂度为$O(N+M)$。 

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
struct E{int from,to,next;} e[MAXM+1];int ecnt,G[MAXN+1];
void addEdge(int u,int v){e[++ecnt]=(E){u,v,G[u]};G[u]=ecnt;}

int gcnt,belong[MAXN+1];//缩成的点数，这个点属于所点后的那个点

stack<int> st;bool inSt[MAXN+1];
int dfn[MAXN+1],low[MAXN+1];int vcnt;
void tarjan(int u)
{
	int i;
	dfn[u]=low[u]=++vcnt;
	st.push(u);inSt[u]=true;
	for(i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else 
			if(inSt[v])
				low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		++gcnt;
		do
		{
			u=st.top();st.pop();
			inSt[u]=false;
			belong[u]=gcnt;
		}
		while(dfn[u]!=low[u]);
	}
}

###[USACO5.3] Network_of_Schools

Tarjan的简单应用

由于所点后续操作十分简单，我们没必要再费内存建另一张缩过点后的图，只需统计缩过后的每一个点的入度与出度。

由于所有入度为零的学校必须得到真传才可以，故A问题的答案即为所有入度为零的点；对于B问题，不仅需要入度为零的点得到真传，还要保证所有点都能肩负起传给其他所有学校的历史重任，即所有点的出度都不能为零。

事实上，只要上述一个条件满足，则另一个条件一定满足（因为只要一个条件满足，那么这张缩过点的图也变成一张连通图了）。故B问题的答案即为入度为零的点数和出度为零的点数两者的最大值。

有一点需要注意，如果最后缩成一个点，需要进行特殊处理。

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
/*
ID:zhangch33
Task:schlnet
LANG:C++
*/
#include<iostream>
#include<cstdio>
#include<stack>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;

const int MAXN=100,MAXM=10000;

int N;

struct E{int from,to,next;} e[MAXM+1];int ecnt,G[MAXN+1];
void addEdge(int u,int v){e[++ecnt]=(E){u,v,G[u]};G[u]=ecnt;}

int gcnt,belong[MAXN+1];//缩成的点数，这个点属于所点后的那个点

stack<int> st;bool inSt[MAXN+1];
int dfn[MAXN+1],low[MAXN+1];int vcnt;
void tarjan(int u)
{
	int i;
	dfn[u]=low[u]=++vcnt;
	st.push(u);inSt[u]=true;
	for(i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else 
			if(inSt[v])
				low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		++gcnt;
		do
		{
			u=st.top();st.pop();
			inSt[u]=false;
			belong[u]=gcnt;
		}
		while(dfn[u]!=low[u]);
	}
}

int inDgr[MAXN+1],outDgr[MAXN+1];

int main()
{
	freopen("schlnet.in","r",stdin);
	freopen("schlnet.out","w",stdout);
	int i;
	scanf("%d",&N);
	for(i=1;i<=N;i++)
	{
		int u=i,v;
		scanf("%d",&v);
		while(v)
		{
			addEdge(u,v);
			scanf("%d",&v);
		}
	}
	for(i=1;i<=N;i++)
		if(!dfn[i]) tarjan(i);
	for(i=1;i<=ecnt;i++)
		if(belong[e[i].from]!=belong[e[i].to])
		{
			++inDgr[belong[e[i].to]];
			++outDgr[belong[e[i].from]];
		}
	int ansA=0,ansB=0;
	for(i=1;i<=gcnt;i++)
	{
		if(inDgr[i]) ++ansA;
		if(outDgr[i]) ++ansB;
	}
	ansB=max(ansA,ansB);
	if(gcnt==1) printf("1\n0\n");
	else printf("%d\n%d\n",ansA,ansB);
	return 0;
}

###[HAOI2006] 受欢迎的牛
这道题更水了，不过因为是本省省选真题，还是说一下：

很明显首先需要缩点，所完点后每一个强联通分量里的牛形成一个命运共同体，也就是说只要缩完后的点是受欢迎的，那么这里边所有的牛都是，我们想到要存一下每一个命运共同体里的牛的数量。

接下来，我们注意到当且仅当缩完后的点中有且只有一个点的出度为零时，这个点中的牛是受欢迎的（如果有两个这样的点，那么整张图就不存在受欢迎的牛），而答案就是这个点中牛的数目。

代码依然不长，在省选中实为送分题

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
#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;

const int MAXN=1000,MAXM=5000;

int N,M;

struct E{int from,to,next;} e[MAXM+1];int ecnt,G[MAXN+1];
void addEdge(int u,int v){e[++ecnt]=(E){u,v,G[u]};G[u]=ecnt;}

stack<int> st;
bool inSt[MAXN+1];
int belong[MAXN+1],gcnt,memNum[MAXN+1];

int dfn[MAXN+1],low[MAXN+1];
int vcnt;
void tarjan(int u)
{
	int i;
	dfn[u]=low[u]=++vcnt;
	st.push(u);inST[u]=true;
	for(i=G[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else 
			if(inst[v])
				low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		++gcnt;
		do
		{
			u=st.top();st.pop();
			inSt[u]=false;
			belong[u]=gcnt;
			++memNum[gcnt];
		}while(low[u]!=dfn[u]);
	}
}

int outDgr[MAXN+1];

int main()
{
	int i;
	scanf("%d%d",&N,&M);
	for(i=1;i<=m;i++)
	{
			int u,v;
			scanf("%d%d",&u,&v);
			addEdge(u,v);
	}
	for(i=1;i<=N;i++)
			if(!dfn[i]) tarjan(i);
	for(i=1;i<=M;i++)
			if(belong[e[i].from]!=belong[e[i].to])
					++outDgr[e[i].to];
	int ans;
	bool exist=false;
	for(i=1;i<=gcnt;i++)
			if(!outDgr[i])
					if(exist)
					{
							exist=false;
							break;
					}else exist=true,ans=i;
	if(exist) printf("%d\n",memNum[ans]);
	else printf("0\n");
	return 0;
}

###[HAOI2010] 软件安装

这道题难道是传说中的依赖背包？我也不清楚。不过很明显的是一定要先用tarjan缩点，然后再跑树上背包。这里有一个技巧，为了成功地跑树上背包，我们将一个超级源点连接到所有入度为零的点，把森林建成一棵树，这样答案就在源点上了。

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
117
118
119
#include<iostream>
#include<cstdio>
#include<stack>
using namespace std;

const int MAXN=100,MAXE=10000,MAXM=500;

int M,N;

struct E{int from,to,next;};
struct CFS//Chain Forward Star
{
	E e[MAXE+1];
	int ecnt,G[MAXN+1];
	void addEdge(int u,int v){e[++ecnt]=(E){u,v,G[u]};G[u]=ecnt;}
} G1,G2;

int weight[MAXN+1],value[MAXN+1];

stack<int> st;bool inSt[MAXN+1];
int dfn[MAXN+1],low[MAXN+1],times;
int belong[MAXN+1];
struct S{int w,v;} scc[MAXN+1];int scnt;
void tarjan(int u)
{
	int i;
	dfn[u]=low[u]=++times;
	inSt[u]=true;
	for(i=G1.G[i];i;i=G1.e[i].next)
	{
		int v=G1.e[i].to;
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else
			if(inSt[v])
				low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u])
	{
		++scnt;
		do
		{
			u=st.top();st.pop();
			inSt[u]=false;
			belong[u]=scnt;
			scc[scnt]={weight[u],value[u]};
		}
		while(low[u]!=dfn[u]);
	}
}

bool inDgr[MAXN+1];

inline void rebuild()
{
	int i;
	for(i=1;i<=G1.ecnt;i++)
		if(belong[G1.e[i].from]!=belong[G1.e[i].to])
		{
			G2.addEdge(belongG1.e[i].from],belong[G1.e[i].to]);
			inDgr[belong[G1.e[i].to]]=true;
		}
}

int dp[MAXN+1][MAXM+1];

void dfs(int u)
{
	int i,j,k;
	//dfs过程
	for(i=G2.G[u];i;i=G2.e[i].next)
	{
		dfs(G2.e[i].to);
		for(j=M-scc[u].w;j>=0;j--)
			for(k=0;k<=j;k++)
				dp[u][j]=max(dp[u][j],dp[u][k]+dp[G2.e[i].to][j-k]);
	}
	//更新本节点的值
	for(i=M;i>=0;i--)
		if(i>=scc[u].w)
			dp[u][i]=dp[u][j-scc[u].w]+scc[u].v;
		else dp[u][i]=0;
	//
}

int main()
{
	int i;
	scanf("%d%d",&N,&M);
	for(i=1;i<=N;i++)
		scanf("%d",&weight[i]);
	for(i=1;i<=N;i++)
		scanf("%d",&value[i]);
	for(i=1;i<=N;i++)
	{
		int u=i,v;
		scanf("%d",&v);
		while(v)
		{
			G1.addEdge(u,v);
			scanf("%d",&v);
		}
	}
	for(i=1;i<=n;i++)
		if(!dfn[i]) tarjan(i);
	rebuild();
	//
	for(i=1;i<=scnt;i++)
		if(!inDgr[i])
		{
			inDgr[i]=true;
			G2.addEdge(0,i);
		}
	dfs(0);
	printf("%d\n",dp[0][M]);
	return 0;
}