并查集是一种树形的数据结构，用于处理一些不相交集合的合并以及查询问题。
情景
现在考虑一种如下的场景：
我有 N 个节点，其中一些节点通过线段进行连接，连接的节点可以通信（不需要两两连接，可以通过相邻的节点转发），现在给出两个节点，需要检查这两个节点是否可以通信。
对于这种场景，最简单的思路就是从其中某个节点开始，递归地遍历另外所有可以通信的节点，然后判断另一个给定的节点是否在所有可通信的节点中，但是实际上，遍历所有可以通信节点的代价是非常高昂的，尤其是在节点数量多，查询次数多的情况下，此时就需要引入一个新的数据结构：并查集
并查集可以很好地处理这类两个节点间是否可以通信的问题。
并查集
并查集有两个主要的步骤：合并 和 查找
为了详细展示这两个步骤，我们先给定如下的一个图：
这个图的某些节点间存在一些边，节点通过这些边互相连通
合并
按秩合并
按秩合并是并查集合并中的一种常见的操作，具体流程如下:
秩可以理解为当前节点在树中的最大层级
- 首先，这 6 个节点并没有连接在一起，所以我们为 1-6 六个节点分别设定
秩的值为 1 - 1 和 2 之间有边连接，于是我们将 1 和 2 合并，设定 1 是父节点，2 指向 1，然后更新节点 2 的秩为 2;
- 2 和 3 之间有边连接，于是我们将 2 和 3 合并，设定 2 是 3 的父节点，然后更新节点 3 的秩为 3;
- 4 和 6 之间有边连接，于是我们将 4 和 6 合并，设定 4 是 6 的父节点，然后更新节点 6 的秩为 2;
- 5 和 6 之间有边连接，于是我们将 5 和 6 合并，因为 6 的父节点已经是 4 了，所以我们设定 5 的父节点是 6，然后更新 5 的秩为 2
当两个集合合并时，秩的概念用来决定把哪棵树作为合并后的根。我们应该将拥有较小秩的树合并到拥有较大秩的树上。这样做的目的是为了保持整体树的平衡，尽量减少树的高度，从而提高后续查找操作（Find）的效率
这样我们就可以建立一个简单的并查集了
路径压缩
在按秩合并的思路中，我们尝试将各个节点通过秩的关系大小进行合并，但是事实上，如果我们只需要关心某些节点是否可以连通，我们可以将所有的子节点都连接到同一个父节点，组成一个最大高度为 2 的树
- 1 和 2 之间有边连接，于是我们将 1 和 2 合并，设定 1 为父节点，2 指向 1;
- 2 和 3 之间有边连接，2 的父节点是 1，于是我们可以压缩路径，让 3 和 1 直接连接，设定 3 是 1 的父节点;
- 4 和 6 之间有边连接，但是 4 的父节点是自己，于是设定 4 为父节点，6 指向 4;
- 5 和 6 之间有边连接，但是 6 的父节点是4，于是将 5 和 4 直接连接;
通过如下上述的操作，我们创建了如下的一个带有路径压缩的并查集:
不难看出，尽管连接的方式不同，但是实际的连通性是没有改变的。
查找
无论是按秩合并还是路径压缩，都可以通过寻找相同根节点的方式来判断是否处于同一个并查集
按秩合并
比如我们想要查找节点 3 和 节点 2 是否可以通信，我们先查找节点 3：
- 首先检查 3 的父节点，可以看到是 2
- 然后我们检查 2 的父节点，可以看到是 1
- 最后我们检查 1 的父节点，可以看到父节点是 1，查找结束
然后我们查找节点 2：
- 节点 2 的父节点是节点 1
- 节点 1 的父节点是节点 1，查找结束
由于两个节点的父节点都是相同的，因此我们认为这两个节点可以通信。
路径压缩
与 按秩合并 相同，我们来判断下 3 和 6 节点能否相互通信
首先检查节点 3：
- 节点 3 的父节点是 节点 1
- 节点 1 的父节点是 节点 1，查找结束
然后检查节点 6：
- 节点 6 的父节点是节点 4
- 节点 4 的父节点是节点 4，查找结束
由于节点 3 和节点 6 的根节点并不相同，所以节点 3 和节点 6 并不能相互通信。
实现
我们简单实现一下上述提到的两种逻辑：
查找
我们先实现下查找的逻辑:
/*
* @Author: NorthCity1984
* @LastEditTime: 2025-01-19 23:22:27
* @Website: https://grimoire.cn
* @NorthCity1984 All rights reserved
*/
// parent[x] 记录了节点 x 的父节点
int find(int x) {
return parent[x] == x ? x : (parent[x] = find(parent[x]));
}
合并
然后简单实现下合并逻辑
按秩合并
/*
* @Author: NorthCity1984
* @LastEditTime: 2025-01-19 23:22:18
* @Website: https://grimoire.cn
* @NorthCity1984 All rights reserved
*/
void to_union(int x1, int x2) {
// 查找两个节点的根节点
int p1 = find(x1);
int p2 = find(x2);
// 两个节点已经合并
if (p1 == p2) {
return;
}
// 按秩合并
if (ranks[p1] > ranks[p2]) {
parent[p2] = p1; // 将较小秩的树p2合并到较大秩的树p1
} else if (ranks[p1] < ranks[p2]) {
parent[p1] = p2; // 将较小秩的树p1合并到较大秩的树p2
} else {
// 如果两个树的秩相等，任意选择一个作为新的根，并更新秩
parent[p2] = p1; // 将p2合并到p1
ranks[p1]++; // 增加新的根的秩
}
return;
}
路径压缩
/*
* @Author: NorthCity1984
* @LastEditTime: 2025-01-19 23:22:18
* @Website: https://grimoire.cn
* @NorthCity1984 All rights reserved
*/
void to_union(int x1, int x2) {
// 路径压缩就比按秩合并简单多了...
parent[find(x1)] = find(x2);
}