在日常的软件开发和算法设计中，我们经常需要处理一类极其有趣的问题：如何高效地维护一组动态变化的、互不相交的集合？ 或者说，当我们在处理复杂的网络连接、社交网络关系或者图像处理中的像素区域时，如何快速判断两个元素是否“属于同一类”
这篇文章将带你深入探讨这一强大的数据结构——不相交集合，更广为人知的名字是并查集。我们将一起从最基础的概念出发，逐步构建起优化的数据结构，并通过实际的代码示例，看看它是如何在毫秒级处理成千上万次连接操作的。
什么是“不相交集合”？
让我们从最基础的定义开始。如果两个集合没有共同的元素，比如集合 A = {1, 2} 和集合 B = {3, 4}，我们就称它们为不相交集合。
在计算机科学中，不相交集合数据结构正是为了维持这类集合而生的。它需要支持两种核心操作，这也是我们后续实现的重点：
- Find（查找）：找出某个特定元素属于哪个集合。通常，我们会通过找到该集合的“代表元”来标识这个集合。
- Union（合并）：将两个不同的不相交集合合并成一个大集合。
实际场景：社交网络中的“朋友圈”
为了让你更直观地理解，让我们设想一个具体的场景。假设我们正在开发一个社交网络的后台系统，我们需要管理一群用户之间的朋友关系。
核心需求：
- 建立关系：用户 x 成为用户 y 的朋友（这意味着我们将 x 和 y 放在同一个社交圈中）。
- 查询关系：判断用户 x 是否是用户 y 的朋友（包括直接朋友和间接朋友，即“朋友的朋友”）。
示例场景：
假设我们有 10 个用户，标记为 a 到 j。现在发生了以下交互：
- a 和 b 成为朋友
- b 和 d 成为朋友
- c 和 f 成为朋友
- …（以此类推）
这时候，系统内部实际上形成了几个互不连通的“圈子”：
- 圈子 G1：{a, b, d} （a 是 b 的朋友，b 是 d 的朋友，那么 a 和 d 也是间接朋友）
- 圈子 G2：{c, f, i}
- 圈子 G3：{e, g, j}
- 圈子 G4：{h} （孤家寡人）
当我们接到查询“a 是否是 d 的朋友？”时，我们实际上是在问：a 和 d 是否在同一个圈子（集合）里？
如何用代码表示这种结构？
在计算机的内存里，我们可以通过几种方式来模拟这种关系，最基础且常用的方式是使用数组和树的概念。
#### 1. 父节点数组
我们可以维护一个整数数组，通常称为 Parent[]。这个数组的索引代表元素，值代表该元素的“上级”。
- 初始状态：刚开始，谁也不认识谁，每个人都是自己的“老板”。所以，
Parent[i] = i。 - 树的形态：当我们合并 a 和 b 时，我们将 a 的 parent 指向 b，或者反过来。这样，所有的连接关系最终会形成一棵或多棵树。每棵树的根节点，就是那个“圈子”的代表元。
识别代表元的铁律：
如果元素 INLINECODE992ba900 是某个集合的代表元，那么 INLINECODEf626ab9b。这是判断根节点的唯一标准。对于普通节点，我们需要顺着父指针一直向上找，直到找到这个“根”。
核心操作详解
让我们来看看这两个核心操作是如何在代码层面实现的。
#### 1. Find（查找）
这是查找的过程。我们要找到元素 i 所在集合的根节点。
逻辑：
- 检查 INLINECODE2be99292 是否等于 INLINECODEaf30bc9c。
- 如果是，恭喜，
i就是根，直接返回。 - 如果不是，递归地在
Parent[i]上调用 Find。
#### 2. Union（合并）
这是合并的过程。我们要把包含元素 INLINECODEc901ba19 的集合和包含元素 INLINECODE5645cfe0 的集合合并。
逻辑：
- 首先分别找出 INLINECODE58773729 和 INLINECODEb4f0531a 的根节点（代表元），我们称之为 INLINECODEc8f71ed2 和 INLINECODE5b849115。
- 如果
iRep == jRep，说明它们本来就在同一个圈子里，不需要操作。 - 否则，我们将其中一个根节点指向另一个根节点（例如
Parent[iRep] = jRep），从而将两棵树连在一起。
代码实现：基础版并查集
为了让你更好地理解，我们来看一看最基础的 C++ 实现。注意，虽然这个版本能工作，但在生产环境中我们还需要对它进行优化（后面会讲到）。
#include
#include
using namespace std;
class UnionFind {
// 存储每个节点的父节点
vector parent;
public:
// 构造函数：初始化并查集
// size: 元素的总数量
UnionFind(int size) {
parent.resize(size);
// 初始状态：每个元素的父节点都是它自己（互不相连）
for (int i = 0; i 2，3->4，然后 1和4 连通，所以 1,2,3,4 都在同一个集合
if (uf.find(1) == uf.find(3)) {
cout << "Yes, 1 and 3 are in the same set." << endl;
} else {
cout << "No, they are not." << endl;
}
return 0;
}
进阶思考：基础版有什么问题？
你可能已经注意到了，上面的 unite 操作非常随意：直接把一棵树挂在另一棵树的根下。在运气不好的情况下，这会导致严重的性能问题。
最坏情况分析：
想象一下，如果我们合并 INLINECODE1ecf3d79, INLINECODEa0c900bd, unite(2, 3)… 这样一直连下去。我们的树会退化成一个链表（Linked List）。
当我们执行 find(0) 时，算法不得不遍历整条链，时间复杂度从近乎 $O(1)$ 变成了 $O(N)$。如果有 10 万个元素，这就是一场灾难。我们需要优化它。
优化 1：按秩合并
核心思想： 谁的“树”长得高，谁就当根。
我们引入一个额外的数组 INLINECODEd8d554b2 或者 INLINECODEbf844d4a，用来记录每个根节点对应的树的高度或大小。在合并时，我们总是把较矮的树挂到较高的树下面。
这样做的好处是，树的高度增长非常缓慢，确保了查找操作的高效性。
#include
#include
using namespace std;
class OptimizedUnionFind {
vector parent;
vector rank; // 用于记录树的高度估算值
public:
OptimizedUnionFind(int size) {
parent.resize(size);
rank.resize(size, 0); // 初始秩都为 0
for (int i = 0; i < size; i++) {
parent[i] = i;
}
}
int find(int i) {
if (parent[i] == i)
return i;
return find(parent[i]);
}
void unite(int i, int j) {
int irep = find(i);
int jrep = find(j);
if (irep == jrep)
return;
// 按秩合并的关键步骤
// 如果 i 的树比 j 的树矮，把 i 挂到 j 下
if (rank[irep] < rank[jrep]) {
parent[irep] = jrep;
}
// 如果 j 的树比 i 的树矮，把 j 挂到 i 下
else if (rank[jrep] < rank[irep]) {
parent[jrep] = irep;
}
// 如果高度一样，随便挂一个，但要把被挂的树的高度 +1
else {
parent[irep] = jrep;
rank[jrep]++;
}
}
};
// 测试优化版本
int main() {
OptimizedUnionFind uf(5);
uf.unite(0, 1);
uf.unite(2, 3);
uf.unite(0, 2);
// 此时树的结构会被平衡，不会退化成链表
cout << "Representative of 0: " << uf.find(0) << endl;
cout << "Representative of 3: " << uf.find(3) << endl;
return 0;
}
优化 2：路径压缩
核心思想： 既然我们要找根，路上遇到的那些“中间商”就没有存在的意义了，直接把它们都连到根上吧！
当我们在执行 INLINECODEf03f3813 时，一旦找到了根节点 INLINECODE014c11d1，我们可以顺便把查找路径上经过的所有节点的 INLINECODEc2451557 都直接指向 INLINECODE274d8fa4。这种技术叫做路径压缩。
效果： 这就像把一条弯曲的树枝强行拉直。配合按秩合并，并查集的操作效率可以逼近 $O(1)$（严格来说是反阿克曼函数，极其缓慢地增长，在实际应用中视为常数）。
#include
#include
using namespace std;
class PathCompressionUF {
vector parent;
vector rank;
public:
PathCompressionUF(int size) {
parent.resize(size);
rank.resize(size, 0);
for (int i = 0; i < size; i++) {
parent[i] = i;
}
}
// 带“路径压缩”的查找函数
// 注意：这是一个非常简洁的递归写法，第一次查找后会扁平化整条路径
int find(int i) {
if (parent[i] != i) {
// 这一行是魔法：让 i 的父节点直接等于 find 返回的根节点
// 递归返回后，路径上的所有节点都会被更新
parent[i] = find(parent[i]);
}
return parent[i];
}
void unite(int i, int j) {
int irep = find(i);
int jrep = find(j);
if (irep == jrep) return;
if (rank[irep] < rank[jrep]) {
parent[irep] = jrep;
} else if (rank[jrep] < rank[irep]) {
parent[jrep] = irep;
} else {
parent[irep] = jrep;
rank[jrep]++;
}
}
};
// 验证路径压缩的效果
int main() {
PathCompressionUF uf(6);
// 构建一条链: 0-1-2-3-4-5
uf.unite(0, 1);
uf.unite(1, 2);
uf.unite(2, 3);
uf.unite(3, 4);
uf.unite(4, 5);
// 第一次 find(0) 会触发路径压缩
// 再次调用 find 时，深度将变为 1
cout << "Finding 0..." << endl;
uf.find(0);
// 你可以打断点调试，观察 parent 数组的变化
// parent[0], parent[1], parent[2] 等应该已经直接指向了根节点 5
return 0;
}
实际应用场景
你可能会问，这个算法在实际中到底哪里用到了？其实它无处不在，特别是在处理图的连通性问题时：
- 无向图的连通分量：给定一张拥有海量节点（比如社交网络的一亿用户）和边（关系），我们需要快速找出存在多少个独立的“圈子”（连通分量）。普通的 DFS/BFS 可能会导致栈溢出，而并查集则非常稳健。
- Kruskal 最小生成树算法：这是图论中的经典算法。在对所有边进行排序后，我们需要依次选择权重最小的边，只要这条边连接了两个不同的集合（即不会形成环）。判断是否形成环，正是并查集的拿手好戏：
find(u) != find(v)。 - 离线查询处理：例如有一组查询，询问两个点是否连通。我们可以先把所有边加进来构建并查集，最后一次性回答所有查询。
常见误区与最佳实践
在实现并查集时，有几个坑是你可能会遇到的：
- 下标越界：如果你输入的节点数据不是从 0 开始，或者是字符串甚至复杂的对象，请务必记得先用 INLINECODEab4df83d 或哈希表将它们映射到连续的整数索引 INLINECODEd5addba0。
- 忘记优化：如果数据量很小（比如 $N 10000$，一定要加上路径压缩，否则你的程序可能会在几个测试用例上超时。
- 误解 INLINECODE98df2a26：记得 INLINECODE76c2e2fe 仅仅是用于合并时的启发式估值，路径压缩可能会改变树的实际高度，但为了效率，我们通常不需要在 INLINECODEd05bebe9 操作中更新 INLINECODEb7e5a8a5 数组，只在
unite时作为参考即可。
总结
我们从最简单的“朋友圈”模型出发，探索了不相交集合这一强大的数据结构。我们学会了如何利用 INLINECODE388ba500 数组来构建森林，理解了 INLINECODE20def33c 和 union 的核心逻辑，并掌握了按秩合并和路径压缩这两项关键优化技术。
现在的你，已经掌握了处理动态连通性问题的利器。接下来，强烈建议你亲自去实现一下 Kruskal 算法或者 LeetCode 上的“省份数量”问题，在实际的编码中感受并查集的优雅与高效。