连通分量的定义

在点集V，边集E的无向图 G 中选取部分段 V’ 和部分边 E’（V’ ⊆ V, E’ ⊆ E）组成的图 G’ 是原图的子图（Subgraph）,特殊地一个子图也是自己的子图。

若一个字图具有连通性，则称其为连通子图（Connected Component）。

若一个图没有其他连通子图包含一个子图 G’ ，那么该字图 G’ 是原图的一个极大连通子图（连通分量、连通块）（Maximal Connected Subgraph）。可以把连通分量理解成一个图中其他“岛屿”互不相连的“岛屿” ，“岛屿”的数量就是连通分量的数量。

graph

例如图中就有3个连通分量，分别是 1-4-5-8，0-2-3 和 6-7。

连通分量的简单应用

查找连通分量包含的节点数或查询连通分量的个数可以使用BFS或DFS并标记vis数组实现。

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
#include <iostream>
#include <vector>
using namespace std;
int n,m,cp,rc;
bool vis[100005];
vector<int> G[100005];
void dfs(int x)
{
	vis[x] = 1;
	rc++;
	for(auto p : G[x])
	{
		if(vis[p] == 0) dfs(p);
	}
}
int main(int argc, char *argv[]) {
	cin >> n >> m;//n为节点数，m为边数
	for(int i = 1;i <= m;i++)
	{
		int u,v;
		cin >> u >> v;
		G[v].push_back(u);
		G[u].push_back(v);
	}
	for(int i = 1;i <= n;i++)
	{
		if(vis[i] == 1) continue;
		rc = 0;
		dfs(i);
		cp++;
	}
}

其中cp记录连通分量的个数，rc记录单个连通分量包含的节点数。

并查集的应用

并查集可以动态维护集合，如合并集合和查找元素是否属于同一个集合。

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

using namespace std;
int n,q,fa[100005];
void init()
{
	for(int i = 1;i <= n;i++)
	{
		fa[i] = i;
	}
}
int find(int x)
{
	if(fa[x] == x) return x;
	else return fa[x] = find(fa[x]);
}
void merge(int x,int y)
{
	int fx = find(x);
	int fy = find(y);
	if(fx == fy) return;
	fa[fx] = fy;
}
int main(int argc, char *argv[]) {
	cin >> n >> q;
	init();
	for(int i = 0;i < q;i++)
	{
		int o,u,v;
		cin >> o;
		if(o == 1)//合并操作
		{
			cin >> u >> v;
			merge(u,v);
		}
		else if(o == 2)//查询操作
		{
			cin >> u >> v;
			if(find(u) == find(v)) cout << "Yes\n";
			else cout << "No\n";
		}
	}
}