1. 从一个实际问题说起为什么需要并查集想象一下你正在开发一个社交网络应用。用户A关注了用户B用户B又关注了用户C。现在你想知道用户A和用户C是否属于同一个社交圈即他们是否通过一系列的关注关系间接相连。或者你在处理一个大型网络中的连通性问题比如判断两个网络节点是否在同一个子网内。这类问题的核心就是动态地维护一组元素的分组关系并高效地回答“两个元素是否属于同一组”以及“合并两个组”的查询。这就是并查集Union-Find或 Disjoint-Set Union DSU数据结构大显身手的地方。它专门为解决这类“动态连通性”问题而生。名字听起来有点学术但拆开看就很简单“并”Union合并两个集合、“查”Find查询元素所属集合、“集”Set集合。它的核心操作就这两个但设计得极其巧妙能在近乎常数时间内完成。我最初接触并查集是在解决一些算法竞赛题目时比如“朋友圈”、“岛屿数量”的变种或者最小生成树算法Kruskal中判断边是否会形成环。那时觉得它像个黑魔法几行代码就能解决看似复杂的问题。但真正理解其内部优化尤其是路径压缩和按秩合并这两种“魔法”的原理与配合才能让你在面临海量数据时依然稳如泰山。今天我们就来彻底拆解这个强大又优雅的数据结构。2. 并查集的核心骨架数组与森林表示法并查集有多种实现方式但最经典、最直观的是使用一个数组来维护。我们通常用一个一维数组parent[]来表示。parent[i]存储的是元素i的“父节点”。如果parent[i] i那么恭喜元素i就是它所在集合的“根”代表元。一个集合的所有元素通过这种父子指针最终都指向同一个根。根节点就是这个集合的“老大”或“代表”。初始状态假设我们有 N 个元素编号从 0 到 N-1。最初每个元素各自为一个独立的集合自己是自己的老大。所以初始化操作就是vectorint parent(n); for (int i 0; i n; i) { parent[i] i; // 我爹就是我自己 }这构建了一片森林森林里有 N 棵孤立的树每棵树只有一个节点。Find查操作给定一个元素x找到它所在集合的根。怎么做顺着parent指针一直往上找直到找到那个parent[root] root的节点。int find(int x) { while (parent[x] ! x) { // 如果x不是根 x parent[x]; // x向上走一步指向它的父亲 } return x; // 返回根节点 }这个操作回答了“你是谁的人”这个问题。如果find(a) find(b)那么 a 和 b 就在同一个集合里。Union并操作给定两个元素a和b把它们所在的集合合并成一个。思路很简单找到a的根rootA和b的根rootB。如果它们不相同就让其中一个根认另一个根做父亲。void unionSet(int a, int b) { int rootA find(a); int rootB find(b); if (rootA ! rootB) { parent[rootA] rootB; // 让rootA认rootB做父亲 } }合并后原本两棵树变成了一棵树。这就是最基础的并查集已经能工作了。但它的效率存在严重问题。考虑一种最坏情况我们依次合并(0,1),(0,2),(0,3), ...(0, n-1)。那么形成的树会退化成一条长长的链。此时执行find(n-1)需要从链尾爬到链头时间复杂度是 O(n)。如果这样的操作很多整体复杂度就接近 O(n²)无法处理大规模数据。注意这个基础版本的unionSet是随意合并的总是让rootA指向rootB。这种随意性正是导致树可能退化成链的元凶之一。3. 优化魔法一路径压缩Path Compression我们的第一个优化目标是Find 操作。退化链导致find要爬很长的路。路径压缩的想法非常直观既然我千辛万苦找到了根为什么不“顺便”把沿途所有人的父亲都直接改成根呢这样下次再查找他们中的任何一个都能一步到位。实现通常用递归简洁而巧妙int find(int x) { if (parent[x] ! x) { // 如果x不是根 parent[x] find(parent[x]); // 递归查找根并将x的父节点直接设为根 } return parent[x]; }让我们拆解一下这行关键的递归调用parent[x] find(parent[x])函数不断递归向上直到找到根root。在递归返回的过程中每一层的parent[x]都被直接赋值为最终返回的root。最终从原始x到根root路径上的所有节点其parent都直接指向了root。这个过程就像把一条长长的链在一次查找后“拍扁”。下图展示了一次find(4)操作前后树结构的变化 假设初始结构1-2-3-4其中-表示父子关系// 执行 find(4) 前 1 | 2 | 3 | 4 // 执行 find(4) 后 (路径压缩) 1 / | \ 2 3 4所有节点都直接挂载到了根节点1下。路径压缩的迭代版本递归虽然简洁但在极端深度下可能有栈溢出风险。迭代版本同样有效int find(int x) { int root x; while (parent[root] ! root) { // 先找到根root root parent[root]; } // 二次遍历进行压缩 while (parent[x] ! root) { int next parent[x]; // 暂存原父节点 parent[x] root; // 将当前节点父指针指向根 x next; // 继续处理原父节点 } return root; }这个版本先找到根再从头遍历一遍路径将所有节点的父指针直接指向根。它需要遍历路径两次但避免了递归。路径压缩的威力经过路径压缩的并查集其find操作的均摊时间复杂度是一个神奇的函数——阿克曼函数的反函数 α(n)。这个函数增长极其缓慢对于任何在宇宙可观测范围内的实际输入比如 n ≤ 10^600α(n) 都不会超过 5。因此在工程实践中我们通常认为经过路径压缩的find操作是近乎常数时间 O(1)的。实操心得在绝大多数情况下使用递归版本的路径压缩就足够了代码更清晰。只有在极其严苛的环境如嵌入式系统栈空间极小或确知数据规模极大且递归深度可能成问题下才需要考虑迭代版本。另外路径压缩会改变树的高度这可能会与我们接下来要讲的“按秩合并”中的“秩”信息产生轻微的不一致秩不再是准确的高度但这种不一致是为了换取更高的查询效率是值得的且不影响正确性。4. 优化魔法二按秩合并Union by Rank现在我们来优化Union 操作。基础版本的unionSet随意指定父子关系是导致树不平衡的另一个原因。优化的思路是总是将更小的树或更矮的树合并到更大的树或更高的树下面。这样能有效控制合并后树的高度增长。我们需要另一个数组rank[]来记录每个根节点对应的树的“秩”Rank。这个“秩”可以理解为树高度的上界一个估计值。初始化时每个节点独自成树高度为0或1定义不同效果等价我们设rank[i] 0。按秩合并的unionSet逻辑如下void unionSet(int a, int b) { int rootA find(a); // find内部已包含路径压缩 int rootB find(b); if (rootA rootB) return; // 已在同一集合无需合并 // 按秩合并将秩小的树合并到秩大的树下 if (rank[rootA] rank[rootB]) { parent[rootA] rootB; } else if (rank[rootA] rank[rootB]) { parent[rootB] rootA; } else { // 两棵树秩相等任意合并但新根的秩需要加1 parent[rootB] rootA; rank[rootA]; // 因为合并后高度增加了1 } }关键点在于最后else分支当两棵树秩相等时无论谁合并到谁下面新树的高度都会比原来增加1因为两棵高度相同的树一棵作为另一棵的子树整体高度1。所以需要将新根的rank加1。为什么“秩”是上界而不是精确高度因为路径压缩会改变树的结构使得树的实际高度可能小于rank值。rank记录的是“在没有路径压缩的情况下这棵树可能达到的最大高度”。它仍然是一个有效的比较指标用于在合并时做出最优决策。即使它不精确也能保证树的高度增长非常缓慢。按秩合并的效果它保证了任何一棵树的高度都不会超过log n以2为底。这是因为每次合并时只有当两棵树秩相等新树的高度才会增加1。而秩为k的树至少包含了2^k个节点可以归纳证明。所以一棵有 n 个节点的树其高度秩最多为log n。这使得即使没有路径压缩单次find操作最坏也是 O(log n)。5. 双剑合璧路径压缩 按秩合并的实战代码与复杂度将两者结合我们就得到了并查集的完全体。这里给出一个完整的C类实现class UnionFind { private: vectorint parent; vectorint rank; // 秩 public: // 初始化n为元素个数 UnionFind(int n) { parent.resize(n); rank.resize(n, 0); // 初始秩为0 for (int i 0; i n; i) { parent[i] i; } } // 查找带路径压缩 int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 递归压缩路径 } return parent[x]; } // 合并按秩合并 void unionSet(int a, int b) { int rootA find(a); int rootB find(b); if (rootA rootB) return; // 按秩合并 if (rank[rootA] rank[rootB]) { parent[rootA] rootB; } else if (rank[rootA] rank[rootB]) { parent[rootB] rootA; } else { parent[rootB] rootA; rank[rootA]; // 秩相同时合并后秩加1 } } // 判断两个元素是否连通 bool connected(int a, int b) { return find(a) find(b); } };时间复杂度分析 当同时使用路径压缩和按秩合并时并查集的每个操作find和union的均摊时间复杂度是 O(α(n))其中 α(n) 是阿克曼函数的反函数。如前所述这是一个比 O(log n) 增长得还要慢得多的函数对于所有实际应用都可以看作是常数时间 O(1)。这意味着你可以对一个包含数百万甚至数十亿元素的集合进行数百万次的合并与查询操作而总时间开销几乎与操作次数成线性关系。这种效率是并查集如此强大的根本原因。重要提示并查集的“常数时间”是均摊意义上的。单次操作的最坏情况可能不是O(1)但一系列操作的平均代价是O(α(n))。在算法竞赛和工程中我们直接按O(1)来估算和设计。6. 并查集的典型应用场景与实战解析理解了原理和实现我们来看看并查集能解决哪些实际问题。它绝不仅仅是算法题里的玩具。6.1 算法竞赛与面试经典题朋友圈LeetCode 547给定一个 N x N 的矩阵 M 表示朋友关系计算朋友圈总数。直接套用并查集遍历矩阵如果M[i][j]1就union(i, j)。最后统计有多少个不同的根即parent[i] i的个数。岛屿数量 IILeetCode 305动态添加陆地实时返回岛屿数量。每添加一块陆地先将其视为一个新岛屿计数1然后检查其上下左右四个方向如果相邻位置也是陆地就进行union操作。如果union成功原本不属于同一个集合说明两个岛屿合并了总岛屿数减1。并查集完美处理了动态合并与查询。等式方程的可满足性LeetCode 990给定一系列等式和不等式判断是否矛盾。处理所有等式ab执行union(a, b)。然后再处理所有不等式a!b检查find(a) find(b)是否成立如果成立则矛盾。6.2 图论算法中的关键角色Kruskal 最小生成树算法这是并查集的“成名战”。算法需要不断选取权重最小的边并判断加入这条边是否会形成环。判断是否形成环就是判断这条边连接的两个顶点是否已经在同一个连通分量中——这正是并查集的connected操作。Kruskal算法的高效很大程度上依赖于并查集的 O(α(n)) 高效合并与查询。动态连通性问题网络连接、电路连通性、社交网络关系演变等凡是需要持续维护“是否相连”状态的问题都是并查集的天然应用场景。6.3 工程与游戏开发中的巧用像素区域连通性分析图像处理在图像中寻找连通区域如斑点检测。可以将每个像素视为一个元素遍历图像将相邻的、颜色相似的像素进行union。最后每个不同的根就代表一个独立的连通区域。这种方法比深度优先搜索DFS在某些情况下更节省内存尤其是处理二值图像时。游戏中的碰撞检测分组在游戏物理引擎中需要快速判断两个物体是否属于同一个碰撞分组。可以为每个碰撞分组维护一个并查集。当需要动态合并分组例如两个机关连接后视为一个整体时union操作非常高效。内存管理中的垃圾回收标记在某些垃圾回收算法如标记-清除的标记阶段需要追踪对象间的引用关系。虽然这不是典型用法但并查集的思想可以用于快速合并相关联的可达对象集合。7. 实现中的细节、陷阱与性能调优即使掌握了核心代码在实际使用中仍有不少细节需要注意。7.1 “秩”的初始化与含义选择我们之前将rank初始化为0代表高度。也有人初始化为1代表集合大小按大小合并。两种方式都能保证对数复杂度且常常混用。关键在于一致性按高度Rankrank初始为0只有两棵树高度相等合并时新根高度才加1。按大小Size需要一个size[]数组初始为1。合并时总是将小树合并到大树下并更新大树的size size[小树]。按大小合并也能保证树高为 O(log n)。在同时使用路径压缩时按秩高度和按大小的性能差异微乎其微。选择哪一种更多是个人习惯。我个人偏好“按秩”因为“秩”这个词更通用地代表了树的某种度量。7.2 路径压缩与按秩合并的交互影响这是一个常被忽略但很有意思的点。路径压缩会改变树的结构降低其实际高度但rank值在合并后就不会再被更新除非发生新的等秩合并。因此rank存储的只是一个上界而不是精确高度。这完全没问题因为按秩合并的逻辑只依赖于rank的相对大小来做出“谁合并到谁下面”的决策而这个相对大小关系即使在路径压缩后依然是有效的压缩只可能降低高度不会让一棵树变得比另一棵更高。所以这两个优化是兼容且互补的。7.3 空间优化技巧标准的并查集需要两个数组parent和rank。如果内存极其紧张可以尝试只用一个parent数组并利用数值的正负或范围来编码“秩”或“大小”信息。例如可以让parent[i]为负值时表示i是根其绝对值代表集合的大小按大小合并。但这样会牺牲一些代码清晰度除非万不得已不建议使用。7.4 针对特定问题的初始化变体有时元素编号不是从0开始的连续整数。我们可以使用哈希表unordered_map来代替数组实现一个泛型的并查集。但这会引入哈希开销性能不如数组。如果可能尽量通过映射将元素转换为连续的整数索引。另外在一些问题中初始状态可能不是所有元素独立而是已知一些连通关系。我们可以在初始化后立即用这些关系执行一系列union操作来构建初始的连通分量。7.5 一个常见的错误在union中忘记使用find的根这是一个新手极易犯的错误// 错误写法 void unionSet(int a, int b) { if (parent[a] ! parent[b]) { // 错误比较的不是根 parent[a] parent[b]; } }必须通过find(a)和find(b)找到它们的根再对根进行操作。直接比较parent[a]和parent[b]毫无意义因为它们可能只是中间节点。8. 从并查集延伸带权并查集与扩展域基础并查集只能维护“是否连通”的关系。但有一类问题需要维护元素间的相对关系。例如已知A和B是同类B和C是敌人C和D是同类问A和D是什么关系判断一系列关于变量相对大小的陈述如A B,B C,C A是否矛盾。这时就需要带权并查集。它在每个节点到其父节点的边上增加一个“权值”这个权值可以表示距离、种类差、大小关系等。在find进行路径压缩时需要同步更新权值在union时需要根据关系推导出两个根节点之间应有的权值。另一种思路是扩展域并查集或称种类并查集。它将每个元素拆分成多个逻辑点例如元素i拆成i_A和i_B分别代表“i是A类”和“i是B类”。然后将“关系”转化为这些逻辑点之间的连通性。例如“i和j是同类”意味着i_A和j_A连通且i_B和j_B连通“i和j是敌人”则可能意味着i_A和j_B连通且i_B和j_A连通。这两种方法都能解决关系推理问题带权并查集更通用但推导复杂扩展域并查集思维更直观但空间开销翻倍。它们都是并查集思想的有力延伸打开了解决更复杂问题的大门。掌握基础并查集后挑战一下带权版本会让你对“维护关系”有更深的理解。