小指针
2022/10/16阅读:22主题:凝夜紫
【数据结构】看完必会的并查集入门攻略2.0
本文是前文的升级版本,在前文的基础上,增加了更详细的讲解,将实现过程分步描述,并且将前文的python实现改成了cpp的实现。
「并查集」是一种思路巧妙,代码很短的数据结构,也因此常常在算法题或者面试中出现。下面我们以一个模板题目作为示例,详细描述并查集的基本原理及使用。
AcWing 836. 合并集合
一共有 n 个数,编号是 1∼n,最开始每个数各自在一个集合中。
现在要进行 m 个操作,操作共有两种:
M a b,将编号为 a 和 b 的两个数所在的集合合并,如果两个数已经在同一个集合中,则忽略这个操作; Q a b,询问编号为 a 和 b 的两个数是否在同一个集合中;
「输入格式」
第一行输入整数 n 和 m。接下来 m 行,每行包含一个操作指令,指令为 M a b 或 Q a b 中的一种。
「输出格式」
对于每个询问指令 Q a b,都要输出一个结果,如果 a 和 b 在同一集合内,则输出 Yes,否则输出 No。每个结果占一行。
「数据范围」
1≤n,m≤105
「输入样例」
4 5 M 1 2 M 3 4 Q 1 2 Q 1 3 Q 3 4
「输出样例」
Yes No Yes
题目描述
有n个数,编号1~n。现在有两个操作:
-
M(merge)。合并两个数到一个集合中,如M a b,则表示a和b合并到一个集合。
-
Q(query)。查询两个数是否在一个集合,如Q a b,查询a和b是否在一个集合当中。
题目分析
分为「常规思路」和「并查集」两部分,读者可以对比这两种方法的不同,来初步理解「并查集」的作用。
常规思路
如果对于两个数,「每个数初始都自己占用一个集合,那么合并两个数就将其中一个数的所属集合变为另外一个」,但是这样做,「在查询的时候则必须遍历两个数的所属集合」,所以单次查询的时间复杂度是O(n)。
使用并查集
概念
「并查集」,从名字中也可以看出来,「这是一个专门负责 合并与查询 的数据结构」。
在并查集中,使用多叉树的形式来维护所有的集合。「使用根节点的编号来作为整个集合的编号,每个节点存储它的父节点,根节点存储它自己」。用p[x]表示x的父节点编号。
-
白色数字:父节点编号;
-
绿色数字:节点本身的编号;

在这里,我们需要明确「集合与节点是包含关系」。
-
「用集合的根节点编号表示一个集合」。比如,也就是初始化之后,1号节点因为「它的节点编号和父节点编号相同」,因此它就是一个集合的根节点,因为它的节点编号是1,所以该集合的编号也是1。
所以,后文所说的"集合1",就是代表「以1号节点为根节点的整个集合」。在上图中,这个集合包含七个元素(未合并前)。
操作:初始化
为了方便后续的并和查的操作,我们在初始化阶段让「每个节点都属于一个单独的集合」,实现上就是「节点编号」等于「它的父节点编号」,如:节点1的父节点也是1。

// 初始化n个集合,每个集合i只有节点i一个元素。
for (int i = 1; i <= n; i ++ )
p[i] = i;
操作:合并
「合并两个节点a和b」。直接将一个节点的所在集合 指向 另外一个节点的所在集合。
如下图,我们把「节点2」合并到「节点1」,既,「集合2的父节点编号 变成 集合1的节点编号」。

// 找到a和b的所属集合
int x = find(a), y = find(b);
// 下面两种方式均是把两个点合并到同一个集合
p[x] = y; // x的父节点是y
p[y] = x; // y的父节点是x
操作:查找
找到元素x属于哪个集合(也就是find
函数)。我们「沿着x的父节点一直向上搜索,直到找到x的最终根节点」。
-
根据「初始化的规则」,我们可以直观的知道,判断「一个点是不是最终根节点」,实际上就是在看「一个点的编号 是否等于 它的父节点的编号」。用代码表示就是
(p[i] == i)
。 -
经过合并之后,「节点的所属集合就会改变」。
如图中「节点2」的所属集合本来是它自己,但是我们合并之后,把整个「集合2」合并到「集合1」上,所表现出来的现象就是「原本节点2的父节点是它自己(2) 表示它是集合2的最终根节点」,合并之后「节点2的父节点变成了节点1,它的父节点不再是它自己,所以它也再属于集合2」。
那么,如何找到「节点2」合并后属于哪个「集合」呢?
我们只要「沿着它的父节点向上找,直到找到最终根节点」(参考概念图中天蓝色的文字描述部分)。
// 当循环停止之后,x就是所属的集合。
while (p[x] != x)
x = p[x];
优化:路径压缩
以概念图为例。
我们发现在「查找」这个操作上,我们要沿着父节点一点点的向上查找,直到找到最终根节点为止。
比如,找到节点7的所属集合,需要查找四次。这个「查找次数和树的高度是成正比例的」,也就是说所需要的时间复杂度是log(n)级别的。
而有一种优化方式,可以把这个复杂度优化到O(1)级别。「在合并的时候,我们直接让所有的节点的父节点都指向所在集合的根节点」。

这种优化方式的好处也很明显,「只需要向上找一次就可以知道某个元素属于哪个集合」。
实现上,我们可以在「查找」操作的过程中,把「对于 非根节点 把它 指向 它所在集合的根节点」。
int find(int x) {
// 路径压缩
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
维护额外信息
考虑这样一个问题:「求某个集合的节点数量」应该怎么办?
只需要「多开一个数组size[]来记录每个集合中的节点数量」。
初始化size[]
,每个集合只有一个节点,既,根节点自己。只有集合合并的时候才会影响到一个集合的节点数量。所以在「合并」的时候,我们只要「把两个集合的节点数量加一起就可以了」。
比如:p[x]=y
该操作将x合并到集合y中,那么显然集合数量的变化就是size[y] += size[x]
。
Code
我们把上面分析的所有代码总结一下,就可以完成本题。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int n, m;
int p[N], size[N];
// 查找
int find(int x) {
// 路径优化
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 合并
int merge(int a, int b) {
int x = find(a), y = find(b);
p[x] = y;
size[y] += size[x];
}
int main() {
cin >> n >> m;
// 初始化
for (int i = 1; i <= n; i ++ ) p[i] = i, size[i] = 1;
while (m -- ) {
char t;
int a, b;
cin >> t >> a >> b;
if (t == 'M') merge(a, b);
else {
int x = find(a), y = find(b);
if (x != y) puts("No");
else puts("Yes");
}
}
return 0;
}
「END」
作者介绍