割点、割边、双连通分量

Nannan Lv5
  2023-08-09 19:12 2023-08-09 19:12 Created   2024-09-30 19:44:57 2024-09-30 19:44:57 Updated      

割点、割边、双连通分量

一、双连通分量、割点、割边

1.割点

定义：对于一个无向图，如果把一个点删除后这个图的极大连通分量数增加了，那么这个点就是这个图的割点(又称割顶)。人话将就是：把这个点删了,一个图会变成不连通的两个部分，我们把这个点称之为割点。

![image-20230727162024521](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230727162024521.png)

2.割边(桥)

定义：和割点有类似的定义，就是把这条边删了，整个图变成不连通的两个部分。

![image-20230727162510097](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230727162510097.png)

3.双连通

首先双连通分为：点双连通和边双连通。

对于一个图来说，点双连通就是：没有割点。边双连通就是：没有割边。

双连通的性质

  • 点：任意两点u，v都存在2条点不相交的简单路径(不经过重复点)。![image-20230727163907650](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230727163907650.png)

  • 边：任意两点u，v都存在2条不经过重复边(这两条路径可以有重复点)的简单路径(不经过重复点)。![image-20230727163748279](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230727163748279.png)

4.双连通分量(Biconnected Component,BCC)

定义：找到一个极大的点集，满足导出子图是点(边)双连通的

显然这个定义并不好理解TAT，那么用人话来说是什么呢？

对于边双来说：我们把每个割边切掉，每个连通块就是边双连通分量。这个就很好理解了，我们把割边都切掉了，它还是连通的，那这个连通块就是边双的，否则如果还有割边，它一定会被切掉。

对于点双来说：比边双稍微复杂一点，因为一个点可能在多个点双里面。我们也是先把割点删了，图变成多个块，然后再把每个割点加入到不同块里面。

看下面的图会好理解一些…QAQ

点双连通分量

割点为：1，3，5，6

将割点一分为二后得到的

![点双连通分量](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230727164407235.png)

边双连通分量

删掉割边

![边双连通分量](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230727164426496.png)

5.双连通分量的缩图

  • 边双：直接缩，缩完以后是一棵树。
  • 点双：由于一个点可能在多个连通块里面，这个东西要怎么去表示呢？对于一个割点我们新建一个点，再向其他点双连边。

点双具体如下图：

  • ![image-20230727171851255](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230727171851255.png)

    ![image-20230727171907591](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230727171907591.png)

6.总结

对于一个连通图，如果任意两点之间至少存在两条没有重复节点的路径，则称这个图为点双连通的（简称双连通）；如果任意两点之间至少存在两条没有重复边的路径，则称该图为边双连通的。点双连通图的定义等价于任意两条边都同在一个简单环中，而边双连通图的定义等价于任意一条边至少在一个简单环中。对一个无向图，点双连通的极大子图称为点双连通分量（简称双连通分量），边双连通的极大子图称为边双连通分量。在每一个点双连通图中，内部无割点；在每一个边双连通图中，内部无桥。

二、算法

回顾前面说的有向图里面的，我们把边分为4种：

  • Tree Edge指树边
  • Back Edge指连向祖先的边(返祖边)
  • Forward Edge指连向子孙的边(前向边，它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点 并不是 当前结点的祖先。)
  • Cross Edge指连向树其他分支的边(横插边,它主要是在搜索的时候遇到了一个已经访问过的结点，但是这个结点 并不是 当前结点的祖先。)
  • 在无向图只存在Tree Edge和Back Edge

那么在无向图里面呢？

我们可以理解为：朝下的边(前向边)当成不存在的，横插边也是当成是不存在的(因为在dfs的过程里面,我们知道横插边它已经是横插了，那连的既不是父亲也不是儿子）。以下图为例：我们在 的时候如果有这条横插边，因为是无向图我们知道可以到，也可以到，那到的时候，那u就会向下到，这样意味着变成了的儿子了，这和我们横插边是矛盾的！

![image-20230727172621353](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230727172621353.png)

那么综上所述，无向图的树只有：返祖边和树边。【这样之后我们tarjan里面的ins数组也就不需要啦，因为ins数组是为了区分返祖边和横插边的，但无向图的dfs树没有横插边所以不用。QAQ介个之前不明白，思考了半天wwwww】

1. 求割边

割边板子

重边是会影响一条边是不是割边的，不能判掉。所以在无向图里面重边的处理要小心。

那么怎么办呢？

(代码中有讲)❗注意：这里要写它边的编号不是它父亲连下来的边的编号，而不是说判这个点是不是父亲。因为单纯判是不是父亲的话，会把重边判成同一条边，这样是错的。因为重边是会影响是不是割边

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 101000;
vector<pair<int,int>>edge[N];
int n,m,idx;
int dfn[N],low[N];
//         low记这个子树里面能跳到的dfn最小的，且未被切掉的(ins[u] = true)
vector<int>bridge;

/*
写法1
//fa_u -> u的这条边的id
void dfs(int u,int id)
{
	dfn[u] = low[u] = ++idx;
	for(auto [v,id2]:edge[u])
	{
		if(!dfn[v])dfs(v,id2);
		if(id != id2){//要看它是父亲直接下来的边，还是返祖边，因为不能把树边当成返祖边去更新low,那么这里只要不是父亲就可以了
		//❗注意：这里要写它边的编号不是它父亲连下来的边的编号，而不是说判这个点是不是父亲
		//因为单纯判是不是父亲的话，会把重边判成同一条边，这样是错的。因为重边是会影响是不是割边
			low[u] = min(low[u],low[v]);
		}
	}
	if(dfn[u] == low[u] && id != -1){
		bridge.push_back(id);
	}

}
*/


/*写法2*/
void dfs(int u,int id)
{
	dfn[u] = low[u] = ++idx;
	for(auto [v,id2]:edge[u])
	{
		if(!dfn[v]){
			dfs(v,id2);
			low[u] = min(low[u],low[v]);
			if(dfn[v] == low[v])bridge.push_back(id2);
		}
		else if(id != id2){
			low[u] = min(low[u],dfn[v]);
		}
	}
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

	cin>>n>>m;
	for(int i = 1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		edge[u].push_back({v,i});
		edge[v].push_back({u,i});
	}

	dfs(1,-1);
	sort(bridge.begin(),bridge.end());
	cout<<bridge.size()<<"\n";
	for(auto x : bridge)
		cout<<x<<" ";
	cout<<endl;
}

2.求割点

什么情况下确定一个点它是割点？

存在一个子树它跳不上去了。比如下图，它最多只能跳到被删去的这个点本身。

![image-20230727191822129](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230727191822129.png)

❗(代码里也有说)这里的我们就不能乱写了，因为我们需要确定这个子树往上跳一步能跳到的地方。所以这里返祖边只能对取。

但是！！！有一个是反例！

当这个点它是根且儿子个数为1，这样的话，我们把这个点删了之后整个图它还是连通的。

![image-20230727192238773](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230727192238773.png)

割点板子 

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<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 101000;
vector<int>edge[N];
int n,m,idx,sz;
int dfn[N],low[N],cut[N];
//         low记这个子树里面能跳到的dfn最小的，且未被切掉的(ins[u] = true)


void dfs(int u,int fa)
{
	dfn[u] = low[u] = ++idx;
	int ch = 0;//记儿子个数
	for(auto v:edge[u])
	{
		if(!dfn[v]){
			dfs(v,u);
			ch++;
			low[u] = min(low[u],low[v]);
			if(low[v]>=dfn[u]) cut[u] = 1;//跳不出去了，说明它是割点
		}
		else if(v != fa)//返祖边
		{
			low[u] = min(low[u],dfn[v]);//❗这里就不能乱写了，要对dfn取min了
		}
		
	}
	if(u == 1 && ch <=1)cut[u] = 0;//特判一下根节点
	sz += cut[u];
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

	cin>>n>>m;
	for(int i = 1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	dfs(1,0);
	cout<<sz<<"\n";
	for(int i = 1;i<=n;i++)
		if(cut[i])
			cout<<i<<" ";
	cout<<"\n";
}

三、割点和割边的应用

例题1：[USACO 2006 Jan, Redundant Paths ]

题意：给一个个点条边的无向连通图，问最少添加多少条边使得成为一个边双连通图。

用人话说就是：问：给你一棵边双搜完之后的树。每次可以覆盖一条路径，问最少多少次能覆盖所有？

bcc-1.png

如上图所示，黑色与绿色边为树边，红色边为非树边。每一条非树边连接的两个点都对应了树上的一条简单路径，我们说这条非树边 覆盖 了这条树上路径上所有的边。绿色的树边 至少 被一条非树边覆盖，黑色的树边不被 任何 非树边覆盖。

我们如何判断一条边是不是桥呢？显然，非树边和绿色的树边一定不是桥，黑色的树边一定是桥。

如何用算法去实现以上过程呢？首先有一个比较暴力的做法，对于每一条非树边，都逐个地将它覆盖的每一条树边置成绿色，这样的时间复杂度为O(nm) 。

结论：下界是叶子个数，因为一条路径最多覆盖2个叶子，那至少要叶子个数条能覆盖完所有。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 101000;
vector<pair<int,int>>edge[N];
int n,m;
int dfn[N],low[N],ins[N],idx,bel[N],cnt;
stack<int>stk;
vector<int>cc[N];

void dfs(int u,int id)
{
	dfn[u] = low[u] = ++idx;
	ins[u] = true;
	stk.push(u);
	for(auto [v,id2]:edge[u])
	{
		if(!dfn[v]){
			dfs(v,id2);
			low[u] = min(low[u],low[v]);
		}
		else if(id != id2){
			low[u] = min(low[u],dfn[v]);
		}
	}
	if(dfn[u] == low[u]){
		++cnt;
		while(1)
		{
			int v = stk.top();
			cc[cnt].push_back(v);
			ins[v] = false;
			bel[v] = cnt;
			stk.pop();
			if(u==v)break;
		}
	}

}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

	cin>>n>>m;
	for(int i = 1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		edge[u].push_back({v,i});
		edge[v].push_back({u,i});
	}

	dfs(1,-1);
	int nleaf = 0;
	for(int i = 1;i<=cnt;i++)
	{
		int cnte = 0;
		for(auto u:cc[i])
		{
			for(auto [v,id] : edge[u])
			{
				cnte += (bel[u] != bel[v]);
			}
		}
		nleaf += (cnte==1);
	}
	cout<<(nleaf+1)/2<<"\n";
}

例题2：POI 2008, BLO

思路：如果不是割点，那删了这个点是不会影响整个图的连通性的，只是这个点本身不连通，那贡献是。如果这个点是割点的话，原本的连通图会被分成若干块：这个点本身+若干被砍下来的子树+剩下的一整个部分。贡献就是那几部分大小的乘积。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 101000;
vector<int>edge[N];
int n,m,idx;
int dfn[N],low[N],sz[N];
//         low记这个子树里面能跳到的dfn最小的，且未被切掉的(ins[u] = true)
ll ans[N];

void dfs(int u,int fa)
{
	dfn[u] = low[u] = ++idx;
	sz[u] = 1;
	ans[u] = n - 1;
	int cut = n - 1;
	for(auto v:edge[u])
	{
		if(!dfn[v]){
			dfs(v,u);
			sz[u] += sz[v];
			low[u] = min(low[u],low[v]);
			if(low[v]>=dfn[u]){
				ans[u] += (ll)sz[v]*(n-sz[v]);
				cut -= sz[v];
			}
		}
		else if(v != fa)//返祖边
		{
			low[u] = min(low[u],dfn[v]);
		}
		
	}
	ans[u] += (ll)cut*(n-cut);
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

	cin>>n>>m;
	for(int i = 1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	dfs(1,0);
	for(int i = 1;i<=n;i++)
		cout<<ans[i]<<"\n";
	cout<<"\n";
}

· 例题3：HNOI2012, 矿场搭建

思路：考虑一个图它是点双(任意删一个点还是连通的)的，那至少需要2个(一个炸了还有另一个)，那方案数就是。如果这个图存在割点，那么我们去看有几个叶子，答案就是叶子个数，方案数就是除了割点以外的所有块的叶子结点的乘积。

总结：对于一般情况，割点会将整个图分为多个连通分量，我们将每个双连通分量看作整个连通块。那么一个双连通分量只需要设置一个出口。我们考虑如果只坍塌一个点，如果出口坍塌，割点就不会坍塌，那么这个分量中其他点可以通过割点到其他分量中，此时等价于同一个双连通分量。我们可以继续将这些点抽象为一个概念：叶子连通块。

什么是叶子连通块？概念引用自

叶子节点是没有出度的点，入度为1，也就是只连了一条边。那么叶子连通块的概念就是：只连接了一个割点的双连通分量。 同时，对于连接两个割点的双连通分量，其中一个割点坍塌，那么另一个割点就不会坍塌，可以通过另一个割点合并到另外一个双连通分量中。而叶子连通块就不行了，如果叶子连通块的割点（叶子的父亲）被切断，那么它就是一个单独的连通块，所以这里一定要设置一个逃生出口。在这里设置一个逃生出口，有weight种选择（weight是节点数）。根据乘法原理，最小个数是叶子连通块的个数；总方案数是所有叶子连通块的weight之积。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 101000;
vector<int>edge[N];
int n,m,idx,cnt;
int dfn[N],low[N],cut[N],sz[N];
//         low记这个子树里面能跳到的dfn最小的，且未被切掉的(ins[u] = true)
stack<int>stk;
vector<int>cc[N];


void dfs(int u,int fa)
{
	dfn[u] = low[u] = ++idx;
	stk.push(u);
	int ch = 0;//记儿子个数
	for(auto v:edge[u])
	{
		if(!dfn[v]){
			dfs(v,u);
			ch++;
			low[u] = min(low[u],low[v]);
			if(low[v]>=dfn[u]){
				cut[u] = 1;//跳不出去了，说明它是割点
				++cnt;
				cc[cnt].clear();
				cc[cnt].push_back(u);
				while(1)
				{
					int w = stk.top();
					cc[cnt].push_back(w);
					sz[cnt]++;
					stk.pop();
					if(w==v)break;
				}
			}
		}
		else if(v != fa)//返祖边
		{
			low[u] = min(low[u],dfn[v]);//❗这里就不能乱写了，要对dfn取min了
		}
		
	}
	if(u == 1 && ch <=1)cut[u] = 0;
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int t = 0;
	while(1)
	{
		cin>>m;
		if(!m)break;
		for(int i = 1;i<=1000;i++)
			edge[i].clear();
		int n = 0;
		for(int i = 1;i<=m;i++)
		{
			int u,v;
			cin>>u>>v;
			edge[u].push_back(v);
			edge[v].push_back(u);
			n = max({n,u,v});
		}
		for(int i = 1;i<=n;i++)
			dfn[i] = low[i] = cut[i] = 0;
		idx = 0,cnt = 0;
		while(!stk.empty())stk.pop();
		for(int i = 1;i<=n;i++)
		{
			if(!dfn[i])
				dfs(1,0);
		}
		cout<<"Case "<<++t<<": ";
		if(cnt==1)
		{
			int n = cc[1].size();
			cout<<2<<" "<<n*(n-1)/2<<"\n";
		}
		else
		{
			int ans1 = 0;
			ll ans2 = 1;
			for(int i = 1;i<=cnt;i++)
			{
				int ncnt = 0;
				for(auto u : cc[i])ncnt += cut[u];
				if(ncnt == 1)
				{
					ans1 += 1;
					ans2 *= (int)cc[i].size()-1;
				}
			}
			cout<<ans1<<" "<<ans2<<"\n";
		}
	}

}

例题4：We Need More Bosses 【边双缩点+树的直径】

题意：点 条边的无向图，保证图连通。找到两个点，使得到必须经过的边最多（一条边无论走哪条路线都经过ta，这条边就是必须经过的边），$2<=n<=310^5,1<=m<=310^5$

思路：因为是必须要走的边，思考什么是必须要走的边？如果有环存在，那可以走的边肯定不是唯一的。在一个边双连通分量里面，任意两点之间至少存在两条无重边的简单路径。那么一个同一个边双内的点是没有必须经过的边的。那么我们可以考虑边双缩点。缩完点以后是一棵树，那么此时任意两点的路径都是唯一的了，我们要求最长的话，那就是树的直径。

四、总结

1.遇到非连通图几乎可以肯定是要求连通分量，不论是无向还是有向图。（可以节约大量思考时间）

2.凡是对边、点的操作，在同一个分量内任意一个点效果相同的，几乎都是缩点解决问题；再粗暴点，几乎求了连通分量都要缩点；

3.一定要考虑特殊情况，如整个图是一个连通分量等。

4.对于双连通分量要分析是边还是点双连通分量。

5.拿到题目要先搞清楚给的是连通图还是非连通图。

对于什么时候用点双，什么时候用边双这个问题，个人感觉是，点双的性质其实比边双要好，因为边双里面允许有割点的存在，边双只强调点集内所有点能相互到达，但点双就有一些更好的性质，比如像吃掉一个点之后剩下的点之间还能相互到达。

  • Title: 割点、割边、双连通分量
  • Author: Nannan
  • Created at : 2023-08-09 19:12:00
  • Updated at : 2024-09-30 19:44:57
  • Link: https://redefine.ohevan.com/2023/08/09/五、割点、割边、双连通分量/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
割点、割边、双连通分量
  1. 割点、割边、双连通分量
    1. 一、双连通分量、割点、割边
      1. 1.割点
      2. 2.割边(桥)
      3. 3.双连通
        1. 双连通的性质
      4. 4.双连通分量(Biconnected Component,BCC)
      5. 5.双连通分量的缩图
      6. 6.总结
    2. 二、算法
      1. 1. 求割边
        1. 割边板子
      2. 2.求割点
        1. 割点板子
    3. 三、割点和割边的应用
      1. 例题1：[USACO 2006 Jan, Redundant Paths ]
      2. 例题2：POI 2008, BLO
      3. · 例题3：HNOI2012, 矿场搭建
      4. 例题4：We Need More Bosses 【边双缩点+树的直径】
    4. 四、总结