1. 项目概述为什么并查集是解决连通性问题的“瑞士军刀”如果你写过一些算法题或者处理过网络节点、社交关系、图像分割这类问题大概率会碰到一个经典场景给你一堆元素你需要快速判断任意两个元素是否属于同一个集合或者需要将两个元素所在的集合合并。最直观的想法可能是用数组或者哈希表来记录每个元素的“老大”但当你需要频繁进行“找老大”和“合并帮派”这两个操作时朴素的实现很容易就超时了。这时候并查集Union-Find就该登场了。并查集也叫不相交集合Disjoint-Set是一种专门为处理这类动态连通性问题而设计的数据结构。它的核心操作只有两个find查找某个元素所属集合的代表元也就是“找老大”和union合并两个元素所在的集合也就是“帮派合并”。别看它结构简单在路径压缩和按秩合并这两种优化技巧的加持下这两个操作的平均时间复杂度可以接近常数级别效率高得惊人。我最初接触它是在解决一个“朋友圈”问题当时用深度优先搜索DFS去遍历数据量一大就卡住了换成并查集后代码简洁了速度也提升了好几个数量级那种感觉就像发现了一把趁手的“神器”。它解决的问题非常普遍社交网络中的好友关系判断两个人是否间接认识、计算机网络中的主机连通性、编译器中的变量等价性分析、游戏开发中的像素区域标记图像分割、最小生成树算法Kruskal算法等等。可以说只要是涉及“分组”和“连通”的场景并查集都是你应该首先考虑的工具之一。这篇文章我就结合自己刷题和项目中的实际使用经验带你彻底搞懂并查集的原理、实现、优化以及那些容易踩的坑。2. 核心原理与数据结构设计从数组到森林的抽象理解并查集关键在于理解它的两种等价视角数组视角和森林视角。数组视角更贴近底层实现便于编码森林视角则更直观有助于理解操作逻辑。2.1 森林视角帮派与树形结构我们可以把每个独立的集合想象成一个“帮派”每个帮派有一个“掌门人”代表元。所有成员都以树形结构组织起来最终都指向掌门人。初始时有 N 个独立的元素我们就创建 N 棵只有一个节点的树每个节点都是自己所在树的根即自己是自己的掌门人。 当需要合并两个元素a和b所在的集合时我们找到a的根节点rootA和b的根节点rootB。如果它们不同说明属于不同帮派那么就把其中一个根节点挂到另一个根节点下面让其中一个帮派归顺另一个。至于谁归顺谁后面“按秩合并”优化会详细说。 查找操作find(x)就是从节点x开始沿着父指针一路向上找直到找到根节点。这个根节点就是元素x所在集合的唯一标识。这个模型非常直观union就是让两棵树合并成一棵find就是寻根问祖。2.2 数组视角底层实现的核心在代码中我们通常用一个长度固定的数组parent来实现这片森林。数组的索引代表元素假设元素编号从 0 到 N-1数组的值代表这个元素的父节点。初始化时每个元素的父节点都是它自己parent[i] i。这对应着森林中 N 棵单节点树。find(x)操作写一个循环或递归函数不断查询parent[x]直到parent[x] x这个x就是根。union(a, b)操作先调用find(a)得到rootA调用find(b)得到rootB。如果rootA ! rootB则执行parent[rootA] rootB或parent[rootB] rootA将一棵树的根指向另一棵树的根。注意这里有一个初学者极易混淆的点。union操作合并的是两个集合的根而不是直接合并a和b这两个节点。错误的写法parent[a] b只是把a个人挂到了b手下如果a原本手下有小弟那么这些小弟就和a断开了联系导致集合分裂。所以必须先find到根再合并根这是并查集操作不可违背的铁律。2.3 复杂度分析与优化动机在最坏情况下如果我们总是将新节点挂到一棵长链的末尾那么这棵树就会退化成一条链表。此时find操作的时间复杂度会退化到 O(N)。对于需要执行数十万甚至上百万次操作的场景这是不可接受的。因此我们必须对朴素的并查集进行优化目标就是让树尽可能保持扁平。两大核心优化技术——路径压缩和按秩合并——应运而生。它们能双管齐下将单次操作的均摊时间复杂度降低到惊人的 O(α(N))其中 α(N) 是增长极其缓慢的反阿克曼函数对于任何在宇宙可观测范围内的实际数据量α(N) 都不会超过 5因此可以认为是常数时间。3. 核心优化技术详解路径压缩与按秩合并理解了基础操作我们来深入拆解让并查集效率产生质变的两大优化。这是并查集最精华的部分也是面试和实际应用中必考必用的内容。3.1 路径压缩让树变扁平的“捷径”路径压缩的核心思想非常巧妙既然find(x)的目的是找到根那么在查找的过程中我们能不能“顺便”把沿途所有节点的父节点都直接指向根呢这样下次再查找这些节点时就能一步到位。实现方式递归版def find(x): if parent[x] ! x: # 如果不是根节点 parent[x] find(parent[x]) # 递归查找根并沿途将父节点设为根 return parent[x] # 返回根节点这个递归实现非常简洁。它不仅在查找根还在返回的过程中将x到根路径上的所有节点的parent都直接指向了最终的根节点。实现方式迭代版 有些语言递归深度可能受限或者为了极致性能可以用迭代实现。def find(x): root x while parent[root] ! root: # 先找到根节点 root root parent[root] # 路径压缩将从 x 到 root 路径上的所有节点直接指向 root while parent[x] ! root: next_node parent[x] parent[x] root x next_node return root迭代版先找到根再重新走一遍路径进行压缩。虽然代码稍长但逻辑清晰。实操心得在大部分情况下递归版的路径压缩就足够了代码也更易读。但在一些极端递归深度可能很大的场景虽然并查集优化后树很扁平深度不大或者追求极限性能时可以考虑迭代版。我个人的习惯是在算法竞赛中用递归版求快在生产环境的底层库中可能会用迭代版以求稳。3.2 按秩合并避免退化成链的“智慧”路径压缩主要优化了“查”而按秩合并则优化了“并”。它的目的是在合并两棵树时总是将“矮”的树接到“高”的树下面从而避免树的高度快速增长为后续的路径压缩创造更好的条件。“秩”可以理解为树高的一个上界估计。我们引入一个额外的数组rank或size。 初始化时每个元素独立成树秩为0或1根据定义可以是高度0也可以是大小1两种定义都可行但合并逻辑稍有不同。按高度合并更常见rank[i]初始为 0。合并时比较两棵树的根rootA和rootB的rank。如果rank[rootA] rank[rootB]则将rootA挂到rootB下。rootB的高度不变。如果rank[rootA] rank[rootB]则将rootB挂到rootA下。如果两者相等则任意选择一方挂到另一方下但作为新根的树的rank需要加 1因为两棵树高度相同合并后整体高度增加了1。按大小合并size[i]初始为 1代表集合的元素个数。合并时总是将元素个数少的集合的根挂到元素个数多的集合的根下。并更新新根的size。两种方式都能有效控制树高。按高度合并更直接地控制了高度这个指标按大小合并则可能在某些特定问题如需要知道集合大小时更方便。在时间复杂度分析上两者都能达到同样的优化效果。带按秩合并的union操作示例按高度def union(a, b): rootA find(a) rootB find(b) if rootA rootB: return # 已经在同一集合无需合并 if rank[rootA] rank[rootB]: parent[rootA] rootB elif rank[rootA] rank[rootB]: parent[rootB] rootA else: # 高度相等任意合并但新根高度1 parent[rootA] rootB rank[rootB] 13.3 优化组合的效果与实现选择路径压缩和按秩合并可以同时使用它们并不冲突。同时使用时rank数组记录的高度信息可能不再是准确的树高因为路径压缩会改变树的结构降低高度但它仍然是一个有效的“秩”的估计能很好地指导合并顺序。在实际编码中一个标准且高效的并查集模板通常包含以下部分parent数组。rank或size数组用于按秩合并。带路径压缩的find函数。带按秩合并判断的union函数。对于是否必须使用按秩合并我的经验是在算法竞赛或对性能要求极高的场景务必同时使用两者。如果只是解决一个简单问题数据量不大可以只使用路径压缩代码更短。但养成好习惯写出完整的优化模板能避免很多潜在的性能陷阱。4. 完整实现与代码模板理论讲完了我们来点实在的。下面给出几个不同语言版本的、同时包含路径压缩和按秩合并的并查集完整模板。你可以直接复制使用并理解每一行的作用。4.1 Python 实现模板Python版本以其简洁性著称非常适合算法原型设计和面试。class UnionFind: def __init__(self, n): # 初始化每个元素的父节点是自己秩为0 self.parent list(range(n)) self.rank [0] * n # 如果按大小合并可以这样初始化 # self.size [1] * n # self.count n # 连通分量个数 def find(self, x): # 路径压缩递归版 if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): # 按秩合并 rootX self.find(x) rootY self.find(y) if rootX rootY: return False # 已连通合并失败 if self.rank[rootX] self.rank[rootY]: self.parent[rootX] rootY elif self.rank[rootX] self.rank[rootY]: self.parent[rootY] rootX else: # 秩相等任意合并新根秩1 self.parent[rootX] rootY self.rank[rootY] 1 return True # 合并成功 def connected(self, x, y): # 判断两个元素是否连通 return self.find(x) self.find(y)模板使用解析__init__: 构造函数传入元素个数n。这里同时初始化了parent和rank。find: 使用了递归形式的路径压缩一行核心代码self.parent[x] self.find(self.parent[x])同时完成了查找和压缩。union: 先找到两个元素的根如果根不同则按秩合并。函数返回一个布尔值表示是否执行了合并操作这在某些场景如Kruskal算法中判断是否添加了边很有用。connected: 一个非常常用的辅助函数封装了两次find和比较操作。4.2 Java 实现模板Java版本更注重严谨和性能适合工程应用。public class UnionFind { private int[] parent; private int[] rank; // private int count; // 可选连通分量计数 public UnionFind(int n) { parent new int[n]; rank new int[n]; // count n; for (int i 0; i n; i) { parent[i] i; rank[i] 0; // 初始高度为0 } } // 带路径压缩的查找 public int find(int x) { // 迭代版路径压缩 while (parent[x] ! x) { parent[x] parent[parent[x]]; // 路径压缩的优化隔代压缩 x parent[x]; } return x; // 递归版同样可用 // if (parent[x] ! x) { // parent[x] find(parent[x]); // } // return parent[x]; } // 按秩合并 public boolean union(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) { return false; } if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootX] rootY; rank[rootY] 1; } // count--; // 合并后连通分量减少 return true; } public boolean connected(int x, int y) { return find(x) find(y); } // public int getCount() { return count; } }Java模板要点在find方法中我给出了迭代版的一个小技巧parent[x] parent[parent[x]]。这被称为“隔代压缩”它虽然没有递归版压缩得那么彻底一次性压到根但在循环中实现简单且效果也很好能显著降低树高。注释中保留了递归版的写法以及连通分量计数count的示例。在Kruskal算法中count可以用来判断是否已形成最小生成树。4.3 C 实现模板C模板追求极致的运行效率。class UnionFind { public: vectorint parent, rank; UnionFind(int n) : parent(n), rank(n, 0) { iota(parent.begin(), parent.end(), 0); // 用0,1,2,...填充parent } int find(int x) { // 路径压缩递归版 if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; // 迭代版路径压缩 // while (parent[x] ! x) { // parent[x] parent[parent[x]]; // x parent[x]; // } // return x; } bool unite(int x, int y) { // 合并有些实现叫union但union是C关键字 int rootX find(x); int rootY find(y); if (rootX rootY) return false; if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX] 1; } return true; } bool connected(int x, int y) { return find(x) find(y); } };C模板注意使用vector存储parent和rank。初始化时使用了iota函数来快速填充parent数组为 0, 1, 2, ...。合并函数命名为unite因为union是C/C的关键字。同样提供了递归和迭代两种find实现。重要提示无论哪种语言核心逻辑都是一致的。选择哪个模板取决于你的使用场景。在在线编程平台刷题时我建议你准备好自己最熟悉的那个模板在解题时快速默写出来能节省大量时间。5. 典型应用场景与实战解析懂了原理和模板我们来看看并查集到底能解决哪些实际问题。我会通过几个经典问题带你一步步分析如何将问题建模成并查集并写出解决方案。5.1 场景一朋友圈问题LeetCode 547问题描述有n个朋友给出一个n x n的矩阵M表示朋友关系。M[i][j] 1表示第i个人和第j个人是直接朋友。朋友关系具有传递性如果 A 是 B 的朋友B 是 C 的朋友那么 A 和 C 也是间接朋友。求总共有多少个朋友圈连通分量。建模与解决初始化创建并查集大小为n。初始时每个人自成一个朋友圈。合并操作遍历矩阵M的上三角或下三角因为矩阵是对称的。当M[i][j] 1时说明i和j是直接朋友调用union(i, j)将他们所在的朋友圈合并。统计结果遍历所有人0到n-1对每个人调用find(i)找到其朋友圈的根。根的不同种类数就是朋友圈的数量。更高效的做法是在并查集内部维护一个count变量初始为n每次成功执行union后count--最终count就是答案。代码要点def findCircleNum(M): n len(M) uf UnionFind(n) for i in range(n): for j in range(i1, n): # 只遍历一半避免重复 if M[i][j] 1: uf.union(i, j) # 统计不同的根 roots set() for i in range(n): roots.add(uf.find(i)) return len(roots)这个问题完美体现了并查集处理“传递性连通关系”的优势。如果用DFS/BFS你需要为每个未访问的人做一次遍历而并查集在构建关系的过程中就自然完成了分组。5.2 场景二岛屿数量 IILeetCode 305 - 离线版思想这是一个动态问题一开始全是水0然后陆续在某个位置添加陆地1每次添加后都需要实时返回当前岛屿的数量。并查集非常适合处理这种动态连通性问题。建模与解决初始化一个m*n大小的并查集以及一个二维数组grid记录当前陆地状态初始全为0水。岛屿数量count初始为0。当在位置(r, c)添加一块陆地时 a. 如果该位置已经是陆地直接返回当前count。 b. 否则将其标记为陆地count先假设它是一个新岛屿。 c. 查看其上下左右四个相邻位置。如果某个邻居是陆地则说明这块新陆地可能与旧岛屿相连。调用union合并新陆地与邻居陆地所在的集合。如果合并成功意味着两个独立的岛屿连接成了一个count--。每次操作后count就是当前的岛屿数。代码逻辑片段def numIslands2(m, n, positions): uf UnionFind(m * n) grid [[0]*n for _ in range(m)] count 0 res [] dirs [(0,1), (1,0), (0,-1), (-1,0)] for r, c in positions: if grid[r][c] 1: # 已是陆地 res.append(count) continue idx r * n c # 二维坐标转一维索引 grid[r][c] 1 count 1 for dr, dc in dirs: nr, nc r dr, c dc if 0 nr m and 0 nc n and grid[nr][nc] 1: nidx nr * n nc if uf.union(idx, nidx): # 合并成功 count - 1 res.append(count) return res这个例子展示了并查集如何优雅地维护动态集合的连通分量个数其效率远高于每次添加陆地后都进行一次全图的DFS/BFS搜索。5.3 场景三等式方程的可满足性LeetCode 990问题描述给定一个字符串数组equations每个元素是ab或a!b的形式。判断所有这些等式和不等式是否能够同时成立。建模与解决由于变量是小写字母最多26个我们可以初始化一个大小为26的并查集。处理所有等式遍历equations对于每个等式ab将变量a和b进行合并union(a_index, b_index)。等式建立了变量的连通关系。检查所有不等式再次遍历equations对于每个不等式a!b检查变量a和b的根是否相同find(a_index) find(b_index)。如果相同说明根据前面的等式推导a和b必须相等这与不等式矛盾返回false。如果所有不等式检查都通过返回true。核心思想并查集在这里维护了变量的等价类。所有通过等式相连的变量属于同一个等价类连通分量。不等式则要求两个变量必须属于不同的等价类。这个“先处理连接关系再验证约束条件”的模式在解决这类约束满足问题时非常常见。5.4 场景四Kruskal 最小生成树算法这是图论中并查集的经典应用。Kruskal算法用于在加权无向图中找出一棵最小生成树。算法步骤将图中所有边按权重从小到大排序。初始化一个并查集每个顶点自成一个集合。按权重从小到大遍历每条边(u, v, w) a. 检查顶点u和v是否已经连通find(u) find(v)。 b. 如果不连通则这条边可以加入最小生成树不会形成环调用union(u, v)合并两个顶点所在的集合并将边权累加。 c. 如果已连通则跳过加入这条边会形成环。当加入的边数达到顶点数 - 1时算法结束。并查集在其中的作用就是高效地判断两个顶点是否已在同一连通分量中从而避免环的产生。如果没有并查集判断连通性需要DFS/BFS会使算法复杂度变差。实战经验在这些应用场景中最关键的一步是问题建模——识别出问题本质是动态的连通性判断或集合合并。一旦确认套用并查集模板往往能迎刃而解。多练习这类问题能快速提升你的“并查集嗅觉”。6. 常见问题、调试技巧与性能陷阱即使理解了原理在实际编码中还是会遇到各种问题。下面是我在大量使用并查集后总结的一些常见坑点和调试心得。6.1 初始化错误问题忘记初始化parent数组为parent[i]i或者忘记初始化rank数组。现象find函数可能陷入死循环如果parent[i]是默认值0或者按秩合并逻辑出错。检查构造函数第一件事就是完成数组的初始化。这是最基础的步骤务必检查。6.2 合并了非根节点问题在union函数中直接parent[a] b。现象导致集合结构破坏。例如原有结构a-rootA,b-rootB错误合并后变成a-ba脱离了原来的集合rootA而rootA下的其他节点再也找不到a了。纠正必须union(find(a), find(b))即合并两个集合的根。6.3 路径压缩的副作用问题路径压缩后树的高度发生变化此时rank数组记录的高度信息不再准确。现象这本身不是问题因为按秩合并中的rank在优化后应被理解为“秩”一个上界而非精确高度。即使不准确它依然能很好地指导合并。不要在路径压缩后去更新rank值这是不必要的也会增加复杂度。6.4 复杂度理解误区问题认为每次find或union都是 O(α(N))。澄清O(α(N)) 是均摊时间复杂度。单次操作在最坏情况下可能达不到这个效率但经过一系列操作后平均每次的成本极低。在算法分析时我们可以放心地将其视为常数时间。6.5 如何调试并查集当程序出现逻辑错误怀疑是并查集问题时可以采取以下方法打印状态在关键操作union后打印parent数组。观察合并是否正确发生根节点是否正确更新。小数据测试构造一个极小的、能复现问题的测试用例手动模拟并查集的操作过程与程序输出对比。可视化对于复杂问题可以尝试在纸上画出元素和操作步骤模拟并查集的变化这是理解其行为最有效的方式。检查find函数确保你的find函数确实实现了路径压缩。可以在调用前后打印相关节点的父节点看是否被正确压缩到根。6.6 空间与时间权衡空间并查集需要 O(N) 的额外空间存储parent和rank数组。对于元素数量巨大的场景例如数千万以上这可能成为瓶颈。此时可以考虑使用哈希表来实现动态的并查集元素ID不一定是连续的整数但常数时间会稍大。时间虽然均摊复杂度极优但初始化仍需 O(N) 时间。如果问题中元素总数 N 很大但实际参与合并操作的元素很少可以考虑使用懒初始化的并查集用字典存储parent和rank只在元素第一次出现时初始化以节省初始化的开销。7. 扩展与变种应对更复杂的需求标准的并查集处理“是否连通”的问题。但实际问题可能更复杂需要对其进行扩展。7.1 带权并查集有时我们不仅需要知道元素是否连通还需要知道它们之间的某种“关系”或“距离”。例如在“除法求值”问题中我们需要处理a / b value这样的关系并查询任意两个变量的商。核心思想在parent数组之外再维护一个weight数组。weight[x]表示节点x到其父节点parent[x]的“权值”比如比值、距离差等。find操作在递归查找根的过程中需要同时更新权值。路径压缩时节点x的新权值是其到根节点的累积权值。union操作已知a到其根ra的权值为w_ab到其根rb的权值为w_b现在要合并ra和rb并根据给定的a和b之间的关系val推导出ra到rb的权值w然后执行parent[ra] rb并设置weight[ra] w。带权并查集是并查集学习中的一个难点但理解后能解决一大类更复杂的关联性问题。关键在于推导出合并时权值的计算公式并在路径压缩时正确维护权值。7.2 可撤销并查集在有些问题中我们需要支持“回退”操作即撤销最近的一次union。标准并查集由于路径压缩破坏了历史结构无法直接撤销。实现方式不使用路径压缩只使用按秩合并按大小合并更好。将每次union操作影响的节点通常是较小的那棵树的根和其原来的父节点信息记录下来。撤销时只需要根据记录的信息恢复parent和size数组即可。这种并查集常用于需要离线处理、分治或回溯的场景。7.3 动态并查集标准并查集大小固定。动态并查集允许在运行时添加新的元素。实现很简单内部使用哈希表字典代替数组来存储parent和rank。当访问一个不存在的元素时将其初始化为一个新的集合父节点为自己秩为0。class DynamicUnionFind: def __init__(self): self.parent {} self.rank {} def find(self, x): if x not in self.parent: self.parent[x] x self.rank[x] 0 return x if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): # ... 合并逻辑与标准版类似注意处理不存在的元素掌握了这些基础、优化、应用和扩展知识你已经具备了在实战中灵活运用并查集解决各类连通性问题的能力。记住并查集不仅仅是一个数据结构更是一种解决问题的思想——将动态的、复杂的连通关系用简单的合并与查找来维护。下次当你遇到需要分组、归类、判断连通性的问题时不妨先想想能不能用并查集