并查集理解与应用(详细版)

一. 并查集的概念

并查集是一种典型的树形结构，在高级数据结构当中属于比较常用的，很多时候可以用来解决一些元素分组的问题。并查集管理一系列不相交的集合，且支持两种操作：

合并（join || union || merge）：把两个不相交的集合合并为一个集合
查询（find）：查询两个元素是否在同一个集合中

二. 并查集的现实描述

$让我们从生活中的具体例子出发来理解并查集的思想(例子纯属虚构)$

1.假设现在有6个人，每个人刚开始的时候相互之间谁也不认识，那么他们自己就是他们所在集合的代表元素：

2.然后豪子和国子认识了，豪子想当国子的老大，国子在豪子的威逼下只能被迫同意了，那么局势就变成了下面这样

3.然后郭子和国子又认识了，郭子想骑在国子头上当老大，但国子表示不服，而且自己以经有老大了，只有豪子同意才可以。于是郭子去找了豪子，我们假设这次郭子在豪子面前服软了，最后郭子也认了豪子当老大，此时局势又发生了变化

4.我们假设现在另外三人的关系又发生了一些变化，现在局势变成了这样

5.后来郭子和姜官又互相不服，和之前一样，又叫各自的老大出来对线，志志面对豪子当然输的很惨，认了豪子做老大，那么原本他下面的两个小弟自然也认了豪子做老大，最后的情况是：

经过了上面这几步变化，如果你有一点数据结构基础的话，到了这里你应该明白了，这其实是一个树状的结构，要寻找每个集合的代表元素，只需要一层一层往上访问父节点（图中箭头所指的圆），最后到达树的根节点（代表豪子的圆）就行了。根节点的父节点就是它自己(即老大的老大就是自己)。现在我们来看看这棵树的样子：

好了，经过上面的例子，我们就已经具备了写出并查集基本代码的思维了，下面让我们来看一道简单的问题

三. 并查集经典例题

样例1
输入

5 3
4 2
1 3
2 5
2
4 5
1 2
1
2
3
4
5
6
7

输出

Yes
No
1
2

解释
编号2、4、5的学生在同一个班级，编号1、3的学生在同一个班级，因此编号4和5的学生在同一个班级，编号1和2的学生不在同一个班级。

思路：
我们首先来回顾一下上面的那几张图，确定这三个操作函数一般情况下该怎么写
(1) 刚开始，每个人所在的集合只有他自己，那么他的上级也就是他自己，所以我们需要做这样的初始化操作

int fa[MAXN]; //MAXN根据题意而定
inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
        fa[i] = i; //使当前位置存储的值与下标的值相等，即先将父节点设为自己
}
1
2
3
4
5
6

(2) 当我们需要确定两人的的老大(上级)是否是同一个人时，我们需要分别对两人进行查询。就是用递归的写法实现对代表元素的查询：一层一层访问父节点，直至根节点（根节点的标志就是父节点是本身，也就是fa[i]==i。要判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同即可。
代码如下

// 寻找
int find(int x)			//查找x的老大
{
	while(fa[x] != x)	//如果x的上级不是自己(说明他自己不是老大(上级))
		x = fa[x];		//x继续找他的上级，直到找到老大为止
	return x;			//返回老大的名字
}
1
2
3
4
5
6
7

$当然你也可以像下面这么写（带路径压缩）$
注意赋值运算符的优先级是没有三目运算符高的，所以冒号后面要用括号把式子括起来

int find(int x) {
    return x == fa[x] ? x : (fa[x]=find(da[x]));
}
1
2
3

使用路径压缩优化后,并查集的时间复杂度已经比较低了,绝大多数不相交集合的合并查询问题都能够解决,如果你再使用按秩合并的话,复杂度大概是O(log* n),比O(log n) 还低,近似于O(1)

(3) 合并操作也是很简单的，先找到两个集合的代表元素(也就是两派的大哥)，然后将前者的父节点设为后者即可，当然也可以将后者的父节点设为前者，如果题目没有特殊要求随意就设定就行，执行逻辑如下：
1、寻找 x 所在集合的代表元素（即老大）；
2、寻找 y 所在集合的代表元素（即老大）；
3、如果 x 和 y 不相等，则随便选一个人作为另一个人的上级，如此一来就完成了 x 和 y 的合并
代码如下

// 合并
void join(int x,int y)                   //现在让x,y分别找各自派别最高级的老大
{
    int fx=find(x), fy=find(y);        //郭子找到了姜官，
    if(fx != fy)                       // 两人的老大显然不是同一个人
        fa[fx]=fy;                    // 志志只好当豪子的小弟了
}
1
2
3
4
5
6
7

(4) 这三个操作搞明白以后这道题你就已经可以写出来了
题目链接放在这里
注意的点：
(1) 在C++中用数组实现并查集主要问题有以下两个：
$1、元素中不能支持负数。因为C++规定数组的下标不能是负数$
$2、数组实现并查集代码量相对有点大，而且可能会造成空间浪费$
$3、使用map或unordered-map可以避免以上问题$
具体代码：

#include
using namespace std;
unordered_map<int, int> mp1; //建立映射
int find(int x) {           //寻找根节点
	while (mp1[x] != x)
		x = mp1[x];
	return x;
}
void join(int y1, int y2) {//合并分支
	if (find(y1) != find(y2))
		mp1[find(y1)] = find(y2);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m, a, b;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) mp1[i] = i; //初始化操作
	while (m--) {
		cin >> a >> b;
		join(a, b); //把a,b加入同一个集合中
	}
	int k;
	cin >> k;
	while (k--) {
		cin >> a >> b;
		if (find(a) == find(b)) //判断查询的两人是否有共同的根节点
			cout << "Yes" << '\n';
		else
			cout << "No" << '\n';
	}
	return 0;
}
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

$到这里的话我们就算理解基本思想了，接下来来看这样4个问题$

四. 补充例题(4道)

$【下面的代码都是可以通过的,重要部分有添加注释,应该比较好理解】$
1. 学校的班级个数
题目链接放在这里

样例1
输入

5 3
4 2
1 3
2 5
1
2
3
4

输出

2
1

解释
编号2、4、5的学生在同一个班级，编号1、3的学生在同一个班级，因此共有两个班级。
代码：

#include
using namespace std;
unordered_map<int, int> mp;
int find(int x) {
	while (mp[x] != x)
		x = mp[x];
	return x;
}
void join(int p1, int p2) {
	if (find(p1) != find(p2))
		mp[find(p1)] = find(p2);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) mp[i] = i;  //初始化
	int a, b;
	while (m--) {
		cin >> a >> b;
		join(a, b);  //合并处理
	}
	int cnt = 0; //用cnt来记录班级个数
	for (auto it : mp) { //遍历整个集合
		if (it.first == it.second) //如果一个人的祖先是他自己,那么在这个题中也可以说他就是班长(即这个班的老大)
			cnt++;  //班级个数随着班长个数的增加而增加
	}
	cout << cnt;
	return 0;
}
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

2. 迷宫连通性
题目链接放在这里

样例1
输入

5 4
4 2
1 3
2 5
1 5
1
2
3
4
5

输出

Yes
1

解释
所有房间都连通，因此输出Yes。
样例2
输入

5 3
4 2
1 3
2 5
1
2
3
4

输出

No
1

解释
编号2、4、5的房间互相连通，编号1、3的房间互相连通，因此没有全部互相连通，输出No。
代码：

#include
using namespace std;
map<int, int> mp1;
int find(int x) {
	while (mp1[x] != x)
		x = mp1[x];
	return x;
}
void join(int y1, int y2) {
	if (find(y1) != find(y2))
		mp1[find(y1)] = find(y2);
}
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) mp1[i] = i;
	int a, b;
	while (m--) {
		cin >> a >> b;
		join(a, b);
	}
	int flag = find(mp1.begin()->first); //将flag定义为第一个房间的祖先
	for (auto it : mp1) {  //遍历整个集合
		if (find(it.first) != flag) { //如果出现某个房间的祖先和其它的不一致
			cout << "No"; //输出No,然后退出程序
			return 0;
		}
	}
	cout << "Yes"; //如果所有房间的祖先都是同一个，则说明整个迷宫是连通的
	return 0;
}
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

3. 学校的班级人数
题目链接放在这里

样例1
输入

5 3
4 2
1 3
2 5
1
2
3
4

输出

2
3 2
1
2

解释
编号2、4、5的学生在同一个班级，编号1、3的学生在同一个班级，因此共有两个班级，人数分别是3和2。
代码：

#include
using namespace std;
unordered_map<int, int> mp1, mp2; //mp1作为并查集,mp2作为《班长,班级人数》的映射
int cmp(pair<int, int> p1, pair<int, int> p2) {
	return p1.second > p2.second; //自定义排序函数，按照班级人数降序排列
}
int find(int x) {
	while (mp1[x] != x)
		x = mp1[x];
	return x;
}
void join(int y1, int y2) {
	if (find(y1) != find(y2))
		mp1[find(y1)] = find(y2);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m, a, b;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) mp1[i] = i;  //初始化操作
	while (m--) {
		cin >> a >> b;
		join(a, b);  //合并操作
	}
	for (auto it : mp1) {
		mp2[find(it.second)]++; 
		//mp2中的映射为《班长,所在班级的人数》,所以当确定当前同学的班长是谁的时候,就让他们班长对应的班级人数加一
	}
	vector<pair<int, int>> v(mp2.begin(), mp2.end()); //将mp2中的对组放入vector中,方便后续进行排序
	sort(v.begin(), v.end(), cmp); //按班级人数从大到小排序，下面就是最后的输出部分了
	cout << v.size() << '\n';      //vector的大小就是所有班级的个数
	for (int i = 0; i < int(v.size()); i++) {
		if (i == 0) cout << v[i].second;
		else cout << " " << v[i].second;
	}
	return 0;
}
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

4.班级最高分
题目链接放在这里

样例1
输入

5 3
88 90 86 92 95
4 2
1 3
2 5
1
2
3
4
5

输出

2
95 88
1
2

解释
编号2、4、5的学生在同一个班级，编号1、3的学生在同一个班级，因此共有两个班级，最高分数分别是编号1的学生的88分、编号5的学生的95分。
代码：

#include
using namespace std;
unordered_map<int, int> mp1, mp2; //mp1作为并查集,mp2作为《学生,分数》的映射集合
vector<int> v;
int find(int x) {
	while (mp1[x] != x)
		x = mp1[x];
	return x;
}
void join(int y1, int y2) {
	int ans1 = find(y1), ans2 = find(y2);
	if (ans1 != ans2) 
	//这个时候就不能再随便选一个作为上级了,根据题意应该是两者中分数高的作为上级
	//这样可以保证最后根节点(即班长)的分数是班级中最高的
		mp2[ans1] < mp2[ans2] ? mp1[ans1] = ans2 : mp1[ans2] = ans1;
}
int main() {
	int n, m, a, b;
	cin >> n >> m;
	for (int i = 1, t; i <= n; i++) {
		cin >> t;
		mp1[i] = i, mp2[i] = t; //初始化操作
	}
	while (m--) {
		cin >> a >> b;
		join(a, b); //合并操作
	}
	for (int i = 1; i <= n; i++) { //按编号遍历所有人
		if (find(i) == i) { //当确定此人为班长的时候
			v.emplace_back(mp2[i]); //把他的分数加入vector中
		}
	}
	sort(v.begin(), v.end(), greater<int>()); //按分数降序排列，下面就是输出部分了
	cout << v.size() << '\n';
	for (int i = 0; i < int(v.size()); i++) {
		if (i == 0) cout << v[i];
		else cout << " " << v[i];
	}
	return 0;
}
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

在这四个题目之后，我们应该对并查集有了一定的了解，也能用它来解决畅通工程和最小生成树之类的问题了，谢谢各位的耐心阅读 (*^▽^*)
212 / 2022.11.18