1. 从“找老大”到“路径压缩”并查集到底在解决什么问题如果你写过一些算法题或者处理过一些需要动态分组、合并、查询关系的场景大概率会碰到一种让人又爱又恨的数据结构——并查集。我第一次接触它是在处理一个社交网络的好友关系问题需要判断两个人是否在同一个朋友圈里。当时我第一反应是这不就是个图遍历吗DFS或者BFS跑一遍不就知道了直到数据量上到百万级别频繁的查询请求直接把我的服务打挂我才意识到问题的严重性。后来一位前辈扔给我一句“用并查集试试”我才真正理解了什么叫“降维打击”。并查集英文叫Union-Find或者Disjoint-Set Union (DSU)。这个名字听起来有点学术但它的核心思想非常生活化我习惯把它叫做“找老大”算法。想象一下你加入了一个公司公司里有不同的部门。你想知道你和另一个同事是不是同一个部门的最直接的办法是什么不是去翻公司的组织架构图而是去问你的“老大”部门领导。如果你们俩的“老大”是同一个人那你们就在同一个部门。如果公司重组两个部门合并了那也很简单让其中一个部门的“老大”认另一个部门的“老大”当老大就行了。并查集干的就是这个事高效地管理一堆元素的动态分组关系支持两种核心操作——合并两个组Union以及查询某个元素属于哪个组Find。它的高效就高效在“找老大”这个过程被优化到了近乎常数级别的时间复杂度。这背后有两个至关重要的“黑科技”路径压缩和按秩合并。很多人学并查集只记住了代码模板却不知道为什么模板要那么写更不理解那些动图里“树”的形态变化到底意味着什么。这篇文章我就想用最直白的语言和多张示意图把并查集从“是什么”、“为什么”到“怎么用”彻底讲透。你会发现它不仅仅是解决“朋友圈”问题在最小生成树Kruskal算法、游戏中的连通块计算、编译器中的变量等价类分析等场景下都是不可或缺的利器。2. 并查集的核心三要素数组、Find与Union要理解并查集我们必须先抛开那些花哨的优化从最朴素、最直观的实现开始。这样你才能明白后来的那些优化到底在解决什么问题。2.1 用数组表示“父子关系”并查集通常用一个一维数组来实现我们称之为parent数组。数组的下标代表每一个元素比如员工编号0, 1, 2...而数组里存储的值代表这个元素的“父节点”或者说“直接上级”。初始状态下每个元素都是自成一派的自己就是自己的老大。所以我们会把parent[i]初始化为i。# 初始化一个大小为 n 的并查集 def __init__(self, n): self.parent [i for i in range(n)] # 初始时每个人的老大都是自己这个数组构成了一片“森林”。每个元素都是一棵树的根节点这棵树目前只有它自己一个节点。2.2 Find操作如何找到真正的“根老大”Find(x)操作的目标是给定元素x找到它所在集合的“根代表”也就是那棵树最顶上的那个“终极老大”。在朴素实现里这非常简单就是沿着parent数组一路向上找直到找到那个parent[i] i的节点。# 朴素Find实现 def find_naive(self, x): while self.parent[x] ! x: # 如果x不是自己的老大 x self.parent[x] # 那就去找x的老大 return x # 返回找到的终极老大这个过程就像你问一个同事“你的部门领导是谁”他告诉了你他的直接领导A。你再问A“你的领导是谁”A告诉你他的领导是B... 一直问到某个人说“我就是最大的领导。”这个人就是你们这个部门的根代表。2.3 Union操作如何合并两个“帮派”Union(x, y)操作的目标是把元素x和元素y所在的两个集合合并成一个。在朴素实现里思路也很直接分别找到x和y的根节点rootX和rootY。如果rootX rootY说明他俩本来就在一个集合里不用合并。否则就把其中一个根节点挂到另一个根节点下面让其中一个“老大”认另一个“老大”当老大。# 朴素Union实现 def union_naive(self, x, y): rootX self.find_naive(x) rootY self.find_naive(y) if rootX ! rootY: self.parent[rootX] rootY # 让rootX的老大变成rootY这里有一个关键选择是把rootX挂在rootY下还是把rootY挂在rootX下在朴素版本中这个选择是随意的。但就是这个看似随意的选择为后面的性能问题埋下了伏笔。注意合并操作永远是对两个集合的根节点进行的。直接修改非根节点的parent值是错误的这会破坏集合的结构。3. 朴素实现的致命伤退化成链表的树现在让我们来看一个最坏情况的例子它揭示了朴素并查集的性能瓶颈。假设我们有5个元素0, 1, 2, 3, 4。初始状态各自为政。 我们按顺序执行以下合并操作union(0, 1),union(1, 2),union(2, 3),union(3, 4)。按照我们朴素的union_naive方法假设总是将前一个的根挂到后一个的根上过程如下union(0,1):find(0)0,find(1)1。将parent[0]设为1。森林状态 1 (根) | 0 2 (根) 3 (根) 4 (根)union(1,2):find(1)1,find(2)2。将parent[1]设为2。森林状态 2 (根) | 1 | 0 3 (根) 4 (根)union(2,3):find(2)2,find(3)3。将parent[2]设为3。森林状态 3 (根) | 2 | 1 | 0 4 (根)union(3,4):find(3)3,find(4)4。将parent[3]设为4。森林状态 4 (根) | 3 | 2 | 1 | 0最终我们得到了一棵非常“瘦高”的树它已经退化成了一个链表这时如果我们执行find(0)就需要从0开始依次访问1, 2, 3, 4总共4步才能找到根节点4。如果元素数量是n最坏情况下Find操作的时间复杂度就退化成了O(n)。这完全违背了我们使用并查集追求近乎常数时间复杂度的初衷。问题的根源在于我们总是随意地将一棵树挂到另一棵树上而没有考虑两棵树的“规模”或“高度”。这会导致合并后的树可能变得非常不平衡。为了解决这个问题我们必须引入优化策略。4. 优化利器一路径压缩Path Compression路径压缩是并查集第一个也是最重要的优化。它的思想非常巧妙既然Find操作的目的是找到根节点那么在找的过程中为什么不“顺手”把沿途经过的所有节点的父节点都直接指向根节点呢这样下次再查找这些节点或者查找它们的子节点时路径就会大大缩短。这就像公司里传八卦A从B那里听到一个消息最终溯源到老板C。路径压缩相当于A在知道消息来自老板C后下次再有人问他消息来源他直接就说“是老板C说的”而不再经过B这个中间人了。4.1 两种实现方式迭代与递归迭代式路径压缩在找到根节点后再重新遍历一遍路径将路径上所有节点的父节点都设为根节点。def find_iter_pc(self, x): root x # 第一遍找到根节点root while self.parent[root] ! root: root self.parent[root] # 第二遍将路径上所有节点的父节点都指向根节点root while self.parent[x] ! root: parent_temp self.parent[x] self.parent[x] root x parent_temp return root递归式路径压缩代码更简洁在递归返回的过程中逐层将父节点指向最终找到的根节点。def find_recursive_pc(self, x): if self.parent[x] ! x: self.parent[x] self.find_recursive_pc(self.parent[x]) # 递归查找并压缩 return self.parent[x]递归版本是更常见的写法它完美体现了“在查找过程中完成压缩”的思想。虽然递归有额外的函数调用开销但在实际应用中由于树经过压缩后会变得非常扁平递归深度很小这点开销可以接受。让我们用之前的退化链表例子看看路径压缩的效果。对退化链表4-3-2-1-0执行find_recursive_pc(0)查找0发现parent[0]1递归查找find(1)。查找1发现parent[1]2递归查找find(2)。查找2发现parent[2]3递归查找find(3)。查找3发现parent[3]4递归查找find(4)。查找4发现parent[4]4返回4。递归返回设置parent[3] 4。递归返回设置parent[2] 4。递归返回设置parent[1] 4。递归返回设置parent[0] 4返回4。操作完成后树的结构变成了4 (根) / | \ 0 1 2 3所有节点都直接指向了根节点4。下次再执行find(0)、find(1)等操作都只需要一步。实操心得在绝大多数情况下只使用路径压缩这一种优化就足以得到非常高效的并查集。它的均摊时间复杂度接近常数O(α(n))其中α(n)是增长极其缓慢的反阿克曼函数对于任何在宇宙可观测范围内的nα(n)都不会超过5。所以你可以简单理解为常数时间。5. 优化利器二按秩合并Union by Rank路径压缩主要优化了Find操作。而Union操作也有优化空间目标就是在合并两棵树时有策略地选择谁挂载谁从而避免树变得过高。这就是“按秩合并”。“秩”Rank可以粗略地理解为树的高度的一个上界。我们使用一个额外的数组rank来记录每个根节点对应的秩。初始时每个节点都是根秩为0或1通常初始化为0或1含义相同代表只有自己一个节点。合并时我们比较两棵树的秩秩不同将秩较小的树的根节点挂到秩较大的树的根节点下。这样合并后新树的高度等于原来较高的那棵树的高度。秩较大的树的根成为新根。秩相同任意选择一棵树挂到另一棵下。但是新根的秩需要加1。因为两棵高度相同的树合并新树的高度会增加1。class UnionFind: def __init__(self, n): self.parent [i for i in range(n)] self.rank [0] * n # 初始化秩为0 def find(self, x): # 带路径压缩的find 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 # 按秩合并 if self.rank[rootX] self.rank[rootY]: # rootX的树更矮把它挂到rootY下 self.parent[rootX] rootY elif self.rank[rootX] self.rank[rootY]: # rootY的树更矮把它挂到rootX下 self.parent[rootY] rootX else: # 两棵树一样高任意挂载但新根秩要1 self.parent[rootY] rootX self.rank[rootX] 1为什么按秩合并有效它保证了树的生长是“谨慎”的。只有当两棵同样高的树合并时树的高度才会增加。这极大地延缓了树退化成链表的进程。单独使用按秩合并可以将Find操作的最坏时间复杂度优化到 O(log n)。6. 强强联合路径压缩 按秩合并在实际应用中尤其是对性能要求极高的场景如算法竞赛、大型系统核心组件我们通常会同时使用路径压缩和按秩合并。这两者结合才能达到理论上最优的均摊时间复杂度 O(α(n))。这里有一个非常重要的细节当同时使用路径压缩时“秩”不再精确等于树的高度而更像是一个“高度的估计值”或“等级”。因为路径压缩会改变树的结构使树变扁但我们在压缩时并不会去更新其他节点的rank值那样做代价太高。所以rank记录的是“未进行路径压缩时树高度的上界”。这并不影响合并策略的正确性因为rank值大的树在合并前确实曾经更高、更庞大。class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [1] * n # 初始高度为1代表只有自己一个节点 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[rootY] rootX self.rank[rootX] 1 return True # 合并成功这个模板就是并查集的“完全体”足以应对99%的挑战。初始化、查找带压缩、合并按秩三个操作都达到了近乎常数时间的效率。7. 并查集实战从“朋友圈”到“最小生成树”理解了原理和模板我们来看看并查集如何解决实际问题。我挑选了两个最经典的应用场景。7.1 应用一LeetCode 547. 省份数量朋友圈问题问题描述有n个城市其中一些城市彼此相连。如果城市a与城市b直接相连且城市b与城市c直接相连那么城市a与城市c间接相连。省份是一组直接或间接相连的城市。给你一个n x n的矩阵isConnected其中isConnected[i][j] 1表示第i个城市和第j个城市直接相连否则为0。返回矩阵中省份的数量。思路解析这就是典型的并查集应用。每个城市是一个元素。遍历矩阵对于每个isConnected[i][j] 1的关系我们就执行一次union(i, j)将城市i和城市j合并到同一个集合省份中。最后统计有多少个元素的parent[i] i即有多少个根节点就有多少个独立的省份。代码实现class Solution: def findCircleNum(self, isConnected: List[List[int]]) - int: n len(isConnected) uf UnionFind(n) for i in range(n): for j in range(i1, n): # 矩阵是对称的遍历一半即可 if isConnected[i][j] 1: uf.union(i, j) # 统计根节点省份的数量 provinces 0 for i in range(n): if uf.find(i) i: # 或者 if uf.parent[i] i provinces 1 return provinces避坑提示统计省份数量时务必使用find(i)来获取根节点而不是直接看parent[i]。因为经过路径压缩后大部分parent[i]直接指向根但为了代码的健壮性兼容未压缩或部分压缩的状态使用find(i)是更安全的做法。7.2 应用二Kruskal算法求最小生成树MSTKruskal算法是求加权无向图最小生成树的经典贪心算法而并查集是其高效实现的关键。算法步骤将图中所有边按权重从小到大排序。初始化一个并查集每个顶点自成一个集合。按权重从小到大遍历每条边(u, v, w) a. 使用并查集检查u和v是否已经连通即find(u) find(v)。 b. 如果不连通则将这条边加入最小生成树并执行union(u, v)将两个顶点所在的集合合并。当最小生成树中的边数达到n-1n为顶点数时算法结束。并查集的作用高效地近乎O(1)时间判断两个顶点是否已在同一连通分量中从而避免成环。如果没有并查集判断连通性需要DFS/BFS时间复杂度为O(VE)会使Kruskal算法的总复杂度从O(E log E)退化到O(E * V)对于稠密图是无法接受的。def kruskal(n, edges): # edges: list of (u, v, weight) uf UnionFind(n) edges.sort(keylambda x: x[2]) # 按权重排序 mst_edges [] total_weight 0 for u, v, w in edges: if uf.find(u) ! uf.find(v): # 如果u和v不连通 uf.union(u, v) # 合并集合 mst_edges.append((u, v, w)) total_weight w if len(mst_edges) n - 1: break # 已找到最小生成树 return total_weight, mst_edges8. 进阶技巧与常见问题排查掌握了标准模板和经典应用你已经能解决大部分问题了。但在实际编码尤其是面试或竞赛中还有一些细节和变种需要留意。8.1 如何维护每个集合的大小或其它属性有时我们不仅需要知道元素是否连通还需要知道每个连通分量里有多少个元素或者维护一些聚合信息如总和、最大值。我们可以在并查集里增加一个size数组。class UnionFindWithSize: def __init__(self, n): self.parent list(range(n)) self.size [1] * n # 每个集合的初始大小是1 def find(self, x): # ... 路径压缩 ... def union(self, x, y): rootX self.find(x) rootY self.find(y) if rootX rootY: return # 按大小合并将小集合挂到大集合下 if self.size[rootX] self.size[rootY]: self.parent[rootX] rootY self.size[rootY] self.size[rootX] else: self.parent[rootY] rootX self.size[rootX] self.size[rootY]按大小合并Union by Size是按秩合并的一种常见变体效果类似都能保证树的高度增长缓慢。8.2 “带权”并查集如何处理有些问题中元素之间的关系不仅仅是“是否连通”还有“权值”或“偏移量”。例如判断一堆等式/不等式是否矛盾LeetCode 399 990或者计算食物链中动物的关系。这就需要“带权并查集”。在带权并查集中parent数组依然记录父节点同时新增一个weight数组记录当前节点到其父节点的“权值”或关系。在Find进行路径压缩时需要同时更新权值在Union时需要根据题目给出的关系方程来推导和设置权值。这是一个更高级的话题但其核心——路径压缩与合并时维护额外信息的思想——是相通的。8.3 调试与问题排查我的并查集为什么出错了如果你写的并查集代码结果不对可以按以下步骤排查初始化检查parent数组是否正确地初始化为parent[i]irank或size数组是否初始化Find函数递归版本的路径压缩返回值是否正确是否是return self.parent[x]而不是return x确保压缩逻辑正确。Union函数最经典的错误没有使用Find得到的根节点进行合并而是直接parent[x] y。必须合并根节点按秩/按大小合并的逻辑判断是否有误特别是两棵树秩相等时秩的更新 (rank[rootX] 1) 是否遗漏Union前是否检查了rootX和rootY是否相等避免无意义的操作。状态查询判断两个元素是否属于同一集合一定要用find(a) find(b)不能直接用parent[a] parent[b]因为它们的直接上级可能不同但终极老大相同。输入边界元素下标是否从0开始题目给的编号是1-based的话需要在初始化时转换为0-based。并查集的代码模板其实非常短小精悍。我建议你彻底理解后形成自己的肌肉记忆。在需要使用时花一分钟默写出来能为你节省大量的调试时间尤其是在紧张的时间限制下。它就像一把瑞士军刀简单但当你真正理解其精妙之处后会发现它能优雅地解决一大类复杂的动态连通性问题。