文章目录
一、并查集概述
1. 定义
2. 作用
3. 主要操作
二、并查集思想
1. 暴力做法
2. 并查集做法
3. 并查集优化
3.1 路径压缩
3.2 按秩合并（使用较少）
4. 并查集实现详见例题——合并集合
三、并查集例题——合并集合
具体实现
1. 实现思路
2. 代码注解
3. 实现代码
四、并查集例题——连通块中点的数量
具体实现
1. 样例模拟
2. 实现思路
3. 代码注解
4. 实现代码
五、并查集例题——食物链（较难）
具体实现
1. 样例分析
2. 实现思路
3. 代码注解
4. 实现代码
一、并查集概述
- 并查集代码很短，思维精巧，在面试和比赛当中是一种很常用的数据结构。
1. 定义
- 并、查、集，这个三个字，其中前面两个字都是动词，第三个字是个名词。
- 集就是集合，就是将一堆元素没有顺序地摆放在同一个地方。
- 因此并查集的本质就是对集合进行操作。
- 并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。
2. 作用
- （1） 将两个集合合并。
- （2） 询问两个元素是否在一个集合当中
3. 主要操作
初始化：把每个点所在集合初始化为其自身。通常来说，这个步骤在每次使用该数据结构时只需要执行一次，无论何种实现方式，时间复杂度均为 O(N) 。
查找：查找元素所在的集合，即根节点。
合并：将两个元素所在的集合合并为一个集合。通常来说，合并之前，应先判断两个元素是否属于同一集合，这可用上面的查找操作实现。
二、并查集思想
1. 暴力做法
对于如下图所示的两个集合，如果我们要判断H和A是否在同一个集合中，我们需要遍历A所在的集合，并逐一判断当前节点是否是H节点，直到最后遍历完整个蓝色集合，才能判断出H节点不在这个集合中。
- 同样的，如果我们需要合并两个集合，就需要遍历整个黄色的集合，将里面的节点一个一个加入到蓝色集合中。两者都是 O(N) 的时间复杂度。
- 暴力做法一般是用来给我们提供优化的思路，整体比较简单易想，因此便不过多叙述。
2. 并查集做法
在我们生成集合的时候，就人为地将集合中的元素之间创建某种关联。那么查询和合并的操作将会省时很多。形成如下图的结构：
- 对结构进行优化，我们可以发现这两个结构其实就是一个树。会形成近乎 O(1) 的时间复杂度。
- 对于每一个点，我们都存储一下他的父节点是谁，当我们想求某个点是否属于集合当中，也就是查询操作时，就可以根据这个点的父节点是不是根节点，如果不是，就继续向上查找，直到找到根节点为止，根节点的编号就是整个集合的编号。因此，可以用这种方式快速进行查询操作。
- 那么，便会产生如下问题：
（1） 如何判断是不是根节点？ 答：if ( p[x] == x ) 。
（2） 如何求 x 的集合编号？ 答：while ( p[x] != x) x = p[x] 。
（3） 如何合并两个集合？ 答：将一个树根节点的父节点设为另一个树。即：px 是 x 的集合编号，py 是 y 的集合编号，使得 p[x] = y 。
3. 并查集优化
3.1 路径压缩
- 思想：每次查找时，如果路径较长，则修改信息，以便下次查找的时候速度更快。
- 实现：（1） 找到根节点。（2） 修改查找路径上的所有节点，将他们都指向根节点。
3.2 按秩合并（使用较少）
很多人有一个误解，就是认为并查集经过路径压缩优化之后，并查集是只有两层的一颗树，其实不是的。因为路径压缩只在查找的时候进行，也只压缩一条路径，所有并查集的最终结构仍然可能是比较复杂的。
思想：应该把简单的树往复杂的树上合并，即把树的深度小的树合并到树的深度大的树中，这样合并之后，每个元素到根结点的距离变成的元素个数最少。
实现：用 rank[ ] 数组来记录每个根结点对应的树的深度（如果不是根结点，则 rank 中的元素大小表示的是以当前结点作为根结点的子树的深度）；一开始，把所有元素的 rank 设为 1 ，即自己就为一颗树，且深度为 1 ；合并的时候，比较两个根结点，把 rank 较小者合并到较大者中去。
4. 并查集实现详见例题——合并集合
三、并查集例题——合并集合
题目描述
一共有 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 ≤ 1e5
输入样例
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例
Yes
No
Yes
具体实现
1. 实现思路
- 见上文。
2. 代码注解
p[N] 是父节点数组。
p[i] = i 所有节点一开始赋值给自己。
int find (int x) 返回 x 的祖宗节点，包含路径压缩。
p[find(a)] = find(b) a 的祖宗节点的父节点等于 b 的祖宗节点，把 a 节点对应集合合并到 b 节点对应集合。
if (find(a) == find(b)) 如果 a 和 b 的祖宗节点一样的话，就说明在同一个集合里面。
3. 实现代码
#include <bits/stdc++.h> using namespace std; const int N = 100010; int p[N]; int find (int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i ++ ) { p[i] = i; } while (m -- ) { char op[2]; int a, b; cin >> op >> a >> b; if (*op == 'M') { p[find(a)] = find(b); } else { if (find(a) == find(b)) { puts("Yes"); } else { puts("No"); } } } system("pause"); return 0; }
