1. 项目概述为什么我们需要并查集如果你写过一些算法题或者处理过一些需要动态维护元素分组关系的数据大概率会碰到一种让人头疼的场景给你一堆元素你需要频繁地判断任意两个元素是否属于同一个集合或者需要将两个不同的集合合并起来。最直观的想法可能是用数组或者字典来记录每个元素的“老大”但当你面对成千上万次“查找”和“合并”操作时简单的遍历查找效率会低得令人发指。这时一个听起来有点抽象但威力巨大的数据结构就该登场了——它就是并查集。并查集英文叫Union-Find或者Disjoint Set Union。它的核心使命就两个合并和查找。合并是把两个不相交的集合合并成一个查找是确定某个元素属于哪个集合通常是找到这个集合的“代表元”。在Python中实现并查集代码可以非常优雅和简洁但其背后优化的思想却非常深刻。它不仅是解决“朋友圈”、“岛屿数量”、“连通性判断”等经典算法题的利器在编译器优化、图像处理、社交网络分析等实际工程领域也有广泛应用。今天我就结合自己多年的刷题和项目经验带你彻底吃透并查集从最朴素的实现到路径压缩、按秩合并等关键优化再到Python下的各种实战技巧和避坑指南。无论你是正在准备面试的新手还是想深化理解的开发者这篇总结都能让你对并查集有一个全新的、透彻的认识。2. 并查集的核心思想与抽象模型在深入代码之前我们必须先建立起正确的思维模型。并查集处理的核心问题是动态连通性。想象一下社交网络一开始每个人都是独立的个体一个独立的集合。当A和B成为朋友时他们就连通了属于同一个“朋友圈”集合。之后如果B又和C成了朋友那么A、B、C就都属于同一个大朋友圈。并查集要高效支持的就是这两种操作union(p, q)连接p和q和find(x)查找x所在集合的代表。2.1 如何表示集合—— “父指针”表示法并查集最巧妙的构思在于它如何表示一个集合。它不显式地存储集合中的所有元素而是使用一种树形结构每个节点指向它的“父节点”。同一个集合中的所有元素最终都会指向同一个根节点这个根节点就可以作为整个集合的“代表元”或“老大”。我们通常用一个数组parent来模拟这个结构。parent[i]存储的是元素i的父节点索引。如果parent[i] i那就恭喜你找到了根节点i就是它所在集合的老大。初始状态假设有N个元素编号0到N-1。最初它们互不相连每个元素自成一派所以每个元素的父节点就是它自己parent [0, 1, 2, ..., N-1]。这形成了N棵只有一个节点的树。查找操作find(x)为了找到元素x属于哪个集合我们需要沿着它的父指针一路向上找直到找到那个父节点是自己的根节点。这个根节点的编号就是集合的ID。合并操作union(x, y)如果我们想把元素x和y所在的集合合并思路很简单先分别找到它们的根节点rootX和rootY。如果rootX rootY说明它们本来就在一个集合里无需操作。否则我们就把其中一个根节点的父指针指向另一个根节点。这样两棵树就变成了一棵树。这个基础模型非常直观但存在一个严重问题树可能会退化成一条很长的链。例如我们总是把新节点挂到某个固定根节点下那么进行find操作时就可能需要遍历整条链时间复杂度退化为O(N)。这显然不是我们想要的。注意理解“父指针”和“根节点代表集合”这个概念是理解所有后续优化的基础。你可以把它想象成一个公司的汇报关系每个员工都有他的直接上级最终的大老板就是根节点。判断两个员工是否在同一家公司就看他们最终的大老板是不是同一个人。2.2 核心优化一路径压缩路径压缩是并查集最重要的优化没有之一。它的目标非常直接在每次执行find(x)操作时顺带把从x到根节点路径上的所有节点的父指针都直接指向根节点。这样做的好处是立竿见影的。经过一次查找后这条路径上的所有节点下次再被查找时都只需要一步就能找到根节点。多次操作后整个树结构会变得越来越扁平近似于一个“星形”结构极大地加速了后续的查找。在Python中路径压缩可以通过递归或迭代两种方式优雅实现。递归写法非常简洁def find(x): if parent[x] ! x: # 如果x不是根节点 parent[x] find(parent[x]) # 递归查找根节点并沿途将父节点设为根 return parent[x] # 返回根节点这段代码的精妙之处在于parent[x] find(parent[x])。它不仅递归地找到了根还在回溯的过程中把当前节点x的父节点直接更新为根节点。迭代写法可能性能稍好且避免了递归深度的限制def find(x): root x while parent[root] ! root: # 先找到根节点root root parent[root] # 路径压缩把路径上所有节点的父节点都设为根 while parent[x] ! root: next_node parent[x] parent[x] root x next_node return root实操心得在绝大多数情况下递归版本的路径压缩已经完全够用而且代码更清晰。除非你处理的并查集规模极大例如元素数超过10^5且递归深度可能引发问题否则建议使用递归版。它的简洁性带来的可读性优势远大于那微乎其微的性能差异。2.3 核心优化二按秩合并路径压缩主要优化了“查”而“并”操作也有优化空间。当我们合并两棵树时如果随意地将一棵树挂到另一棵树下也可能导致树的高度不必要的增长。虽然路径压缩后续会修复但一个良好的合并策略可以延缓树高度的增长。“按秩合并”中的“秩”通常指树的高度的一个上界或者树的节点数量。我们使用一个额外的数组rank来记录每个根节点对应的树的秩。合并时我们总是将秩较小的树的根挂到秩较大的树的根下面。这样做可以保证合并后的新树其秩不会大于原最大秩1。特别是当两棵树秩相等时合并后新树的秩会增加1。这个策略能有效地控制树的高度使得find操作的平均时间复杂度更低。def union(x, y): rootX, rootY find(x), find(y) if rootX rootY: return # 按秩合并 if rank[rootX] rank[rootY]: parent[rootX] rootY elif rank[rootX] rank[rootY]: parent[rootY] rootX else: # 两棵树秩相等任意合并但被挂接的树秩要加1 parent[rootY] rootX rank[rootX] 1为什么“秩”用高度上界而不用精确高度因为路径压缩会改变树的高度维护精确高度的开销很大。而“秩”是一个在路径压缩时不需要更新的保守估计它只在合并时被比较和更新实现起来更简单高效。重要提示路径压缩和按秩合并是正交的可以同时使用。同时使用这两种优化的并查集其每次操作的摊还时间复杂度可以接近常数级别 O(α(n))其中α(n)是增长极慢的反阿克曼函数对于任何实际应用中的nα(n)都不会超过5。这意味着在工程实践中你可以认为并查集的操作是常数时间的。3. Python实现并查集的完整代码与详解有了理论铺垫我们来看一个功能完整、优化到位的Python并查集类。这个模板足以应对99%的算法题目和一般性工程需求。class UnionFind: 并查集 (Union-Find) 数据结构实现包含路径压缩和按秩合并。 def __init__(self, n: int): 初始化并查集。 :param n: 元素个数元素编号从 0 到 n-1。 self.parent list(range(n)) # 初始时每个元素的父节点是自己 self.rank [1] * n # 初始时每棵树的秩为1 self.count n # 当前连通分量集合的个数 def find(self, x: int) - int: 查找元素x所在集合的根节点代表元附带路径压缩。 :param x: 元素索引 :return: 根节点索引 if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) # 递归压缩路径 return self.parent[x] def union(self, x: int, y: int) - bool: 合并元素x和y所在的集合。 :param x: 元素索引 :param y: 元素索引 :return: 如果x和y原本不在同一集合合并成功返回True否则返回False。 root_x self.find(x) root_y self.find(y) if root_x root_y: return False # 已经在同一集合无需合并 # 按秩合并 if self.rank[root_x] self.rank[root_y]: self.parent[root_x] root_y elif self.rank[root_x] self.rank[root_y]: self.parent[root_y] root_x else: # 秩相等任意合并并将新根的秩加1 self.parent[root_y] root_x self.rank[root_x] 1 self.count - 1 # 合并后连通分量减少1 return True def is_connected(self, x: int, y: int) - bool: 判断元素x和y是否属于同一个集合。 :param x: 元素索引 :param y: 元素索引 :return: 是否连通 return self.find(x) self.find(y) property def component_count(self) - int: 获取当前连通分量集合的数量。 :return: 连通分量个数 return self.count3.1 代码逐行解析与设计抉择初始化__init__:self.parent list(range(n)): 这是创建列表最Pythonic的方式生成了[0, 1, 2, ..., n-1]。比写循环更简洁高效。self.rank [1] * n: 同样用列表乘法初始化秩数组。初始高度为1是合理的因为每个节点自成一棵树。self.count n: 这个变量非常实用它动态记录了当前有多少个独立的集合。在解决“岛屿数量”或“连通分量计数”问题时无需再遍历整个parent数组去统计不同的根直接返回self.count即可将O(N)的操作降为O(1)。查找find:采用了递归式路径压缩。self.parent[x] self.find(self.parent[x])这行代码是灵魂所在。它确保了在查询结束后从x到根路径上的所有节点都直接指向根。递归深度在优化后通常很浅不用担心栈溢出问题。如果实在担心可以使用前面提到的迭代版本。合并union:首先通过两次find获取根节点。注意find操作本身已经完成了路径压缩。比较rank进行按秩合并。这里我选择当秩相等时将root_y挂到root_x下并将root_x的秩加1。这个选择是任意的反过来也行。函数返回一个bool值指示是否执行了合并操作。这个返回值在某些场景下很有用比如在Kruskal算法中只有成功合并的边才会计入最小生成树。self.count - 1: 这是维护连通分量数量的关键。每次成功合并两个不同集合总集合数就减1。连通性判断is_connected:这是一个便捷方法。内部就是比较根节点是否相等。注意它必须调用find而不是直接比较parent[x]和parent[y]因为非根节点的父节点可能不是集合的代表元。分量计数component_count:使用了property装饰器使其可以像属性一样访问 (uf.component_count)而不是方法调用 (uf.component_count())更加符合直觉。3.2 针对不同场景的变体实现上面的模板是通用版本。在实际应用中根据问题特点我们可以进行微调。变体一不维护秩仅使用路径压缩如果你的问题规模不是特别大或者你追求极致的代码简短可以省略rank数组在合并时随意挂接。仅凭路径压缩效率也已经非常高。这时的union操作会简化为def union(self, x, y): root_x, root_y self.find(x), self.find(y) if root_x ! root_y: self.parent[root_y] root_x # 或 self.parent[root_x] root_y self.count - 1 return True return False何时选择在算法竞赛或笔试中为了节省编码时间我经常使用这个简化版。它对于绝大多数题目已经足够快。变体二基于集合大小的合并有时问题关心的是集合的大小元素个数。例如“朋友圈”问题里可能需要知道最大的朋友圈有多少人。我们可以将rank数组的含义从“高度”改为“集合大小”。def __init__(self, n): self.parent list(range(n)) self.size [1] * n # 记录每个根节点对应的集合大小 self.max_size 1 # 记录最大集合大小 def union(self, x, y): root_x, root_y self.find(x), self.find(y) if root_x root_y: return # 将小集合合并到大集合 if self.size[root_x] self.size[root_y]: root_x, root_y root_y, root_x # 交换确保root_x是大集合的根 self.parent[root_y] root_x self.size[root_x] self.size[root_y] self.max_size max(self.max_size, self.size[root_x])这种“按大小合并”同样能保证树高度的对数级别增长是“按秩合并”的一种常见替代方案。4. 并查集经典应用场景与解题套路理解了实现我们来看看并查集到底能解决哪些问题。它绝不仅仅是“判断连通性”那么简单。4.1 场景一动态连通性问题这是并查集的“本职工作”。题目通常会给你一些节点和一系列连接操作或查询操作要求你实时回答两个节点是否连通。例题模板有N个节点初始时互不连通。随后给你一个操作列表每个操作要么是union(a, b)要么是query(a, b)询问a和b是否连通。你需要对每个查询给出答案。解题套路初始化一个大小为N的并查集。遍历操作列表如果是合并操作直接调用uf.union(a, b)。如果是查询操作调用uf.is_connected(a, b)并将结果保存。返回所有查询结果。关键点这类问题通常直接套用模板即可难点可能在于如何将题目描述中的“节点”映射到并查集的整数索引上。可能需要用到字典哈希表来建立映射关系。4.2 场景二岛屿类问题二维网格连通分量LeetCode上经典的“200. 岛屿数量”是并查集的经典应用。给定一个由1陆地和0水组成的二维网格计算岛屿的数量。解题套路并查集解法初始化并查集大小为网格中单元格的总数rows * cols。但注意我们只关心陆地单元格。遍历整个网格如果当前单元格是水跳过。如果当前单元格是陆地先将其视为一个独立的岛屿在心理计数上但并查集初始化时所有节点都是独立的。查看当前陆地单元格的右方和下方的相邻单元格避免重复合并。如果相邻单元格也是陆地就将当前单元格与相邻单元格在并查集中合并起来。union操作会自动将属于同一个岛屿的陆地单元格归入同一个集合。遍历结束后我们需要知道有多少个独立的集合岛屿。但这里不能直接返回uf.component_count因为并查集包含了所有水域单元格它们也是独立的集合。正确的做法是只统计那些是陆地、且其父节点是自己的单元格数量。或者更高效的是在初始化时只将陆地单元格加入并查集但这需要额外的数据结构来记录陆地节点索引。一个常见的技巧是在遍历合并过程中如果成功合并两个陆地就将岛屿计数减1。初始岛屿数等于陆地单元格总数每成功合并一次岛屿数减1。def numIslands(grid): if not grid: return 0 rows, cols len(grid), len(grid[0]) # 初始化并查集这里使用简化版只路径压缩 parent {} def find(x): if parent[x] ! x: parent[x] find(parent[x]) return parent[x] def union(x, y): rootX, rootY find(x), find(y) if rootX ! rootY: parent[rootY] rootX return True return False # 第一遍遍历初始化所有陆地的父节点为自己 for r in range(rows): for c in range(cols): if grid[r][c] 1: node_id r * cols c # 将二维坐标映射为一维ID parent[node_id] node_id count sum(grid[r][c] 1 for r in range(rows) for c in range(cols)) # 初始岛屿数陆地数 # 第二遍遍历合并相邻陆地 for r in range(rows): for c in range(cols): if grid[r][c] 1: cur_id r * cols c # 只检查右和下避免重复 if r 1 rows and grid[r1][c] 1: if union(cur_id, (r1)*cols c): count - 1 if c 1 cols and grid[r][c1] 1: if union(cur_id, r*cols (c1)): count - 1 return count避坑指南二维转一维必须熟练掌握id row * cols col这个映射公式这是处理网格类并查集问题的基本功。方向处理只需检查两个方向例如右和下即可覆盖所有相邻关系检查四个方向会导致重复合并虽然结果正确但效率低。union操作本身是幂等的但重复判断浪费计算。边界检查在访问相邻单元格前务必检查数组下标是否越界。计数技巧上述“初始计数合并减一”的方法比最后再遍历parent数组统计根节点要高效直观。4.3 场景三等式方程的可满足性LeetCode “990. 等式方程的可满足性”是并查集处理“等价关系”的完美例子。给定一个字符串数组equations每个元素是ab或a!b的等式/不等式判断所有方程是否可能同时成立。解题套路等式具有传递性ab且bc则ac这正是并查集所擅长的。不等式则要求两个变量不在同一个集合。第一遍遍历所有equations处理所有的等式。将等号两边的变量进行合并建立起连通关系。第二遍遍历所有equations处理所有的!。检查不等号两边的变量如果它们的根节点相同即is_connected返回True则产生了矛盾直接返回False。如果所有不等式检查都通过则返回True。关键点变量映射变量是小写字母但可能是多个字母组成的字符串。我们需要一个字典将变量名映射到并查集的整数索引。两阶段处理必须先处理所有等式构建出完整的等价关系集合然后再用这些集合去校验不等式。顺序不能颠倒。def equationsPossible(equations): # 给所有出现的变量分配一个唯一ID var_id {} id_counter 0 for eq in equations: a, b eq[0], eq[3] if a not in var_id: var_id[a] id_counter id_counter 1 if b not in var_id: var_id[b] id_counter id_counter 1 uf UnionFind(id_counter) # 使用之前定义的UnionFind类 # 第一遍处理所有等式 for eq in equations: if eq[1] : a_id, b_id var_id[eq[0]], var_id[eq[3]] uf.union(a_id, b_id) # 第二遍检查所有不等式 for eq in equations: if eq[1] !: a_id, b_id var_id[eq[0]], var_id[eq[3]] if uf.is_connected(a_id, b_id): return False return True4.4 场景四最小生成树Kruskal算法Kruskal算法是并查集的“高光”应用场景之一。用于在一个加权无向图中找出一棵最小生成树。算法步骤将图中所有边按权重从小到大排序。初始化一个并查集包含图中所有顶点每个顶点自成一个集合。按权重从小到大遍历每条边(u, v, w) a. 使用并查集检查顶点u和v是否已经连通即是否在同一个集合中。 b. 如果不连通则这条边可以加入最小生成树不会形成环。调用uf.union(u, v)合并这两个顶点所在的集合并将边权累加到结果中。 c. 如果连通则跳过这条边加入它会形成环。当并查集中只剩下一个连通分量或者已经选择了N-1条边对于N个顶点的树时算法结束。并查集的作用高效地近似O(1)时间复杂度判断加入一条边后是否会形成环这是Kruskal算法高效的关键。def kruskal(n, edges): :param n: 顶点个数 :param edges: 边列表每个元素为 (u, v, w) :return: 最小生成树的权重和 uf UnionFind(n) edges.sort(keylambda x: x[2]) # 按边权排序 mst_weight 0 edges_used 0 for u, v, w in edges: if uf.union(u, v): # 如果成功合并说明这条边被加入MST mst_weight w edges_used 1 if edges_used n - 1: # 已经找到足够边提前结束 break # 如果 edges_used ! n-1说明图不连通无法形成生成树 return mst_weight if edges_used n - 1 else -1实操心得在Kruskal算法中并查集的union操作返回的布尔值非常有用可以直接用来判断边是否被采纳。同时维护一个edges_used计数器可以在找到N-1条边后提前终止循环这是一个有效的优化。5. 高级技巧、常见陷阱与性能优化掌握了基本应用后我们来看看一些更深入的话题和容易踩的坑。5.1 并查集能处理“断开连接”吗标准的并查集只支持合并和查询不支持删除边或将一个集合拆分开。这种数据结构被称为“增量连接”数据结构。如果你需要支持删除操作问题会变得复杂得多通常需要借助其他高级数据结构如“离线处理”、“线段树分治”或“可撤销并查集”这已经超出了基础并查集的范畴。在面试或日常使用中如果问题涉及“断开”首先要怀疑是否真的需要并查集或者是否有其他建模方式可以避免删除操作。5.2 路径压缩与按秩合并的兼容性这是一个经典问题在find函数中进行路径压缩时树的“高度”发生了变化那么我们为“按秩合并”而维护的rank数组还准确吗答案是不准确但没关系。我们之前定义rank为树高度的“上界”或“估计值”而不是精确高度。路径压缩可能会降低树的高度但不会让rank值高于实际高度。在合并时我们比较的是两个根节点的rank值这个比较依然是有效的——rank值大的树其真实高度肯定不会小。即使rank值因为路径压缩而变得“虚高”也不会影响合并的正确性顶多让合并策略不那么“最优”但整体的摊还复杂度保证依然成立。因此路径压缩和按秩合并可以安全地一起使用。5.3 如何获取每个集合的所有元素标准的并查集只维护了父指针关系要获取某个集合的所有成员需要遍历所有元素对每个元素调用find然后根据根节点进行分组。这是一个O(N)的操作。def get_components(uf, n): 返回一个字典key为根节点value为该集合所有元素的列表 components {} for i in range(n): root uf.find(i) if root not in components: components[root] [] components[root].append(i) return components如果业务中需要频繁查询集合成员并查集可能不是最佳选择需要考虑其他数据结构。5.4 并查集的时间复杂度与空间复杂度时间复杂度单次操作find,union,is_connected在同时使用路径压缩和按秩合并的情况下摊还时间复杂度是 O(α(n))其中α(n)是反阿克曼函数增长极其缓慢对于任何实际有意义的n比如n小于宇宙中的原子数α(n) 5。因此在工程上可以认为是常数时间。构建并查集O(N)。执行M次操作近似 O(M * α(N)) ≈ O(M)。空间复杂度O(N)用于存储parent和rank数组。5.5 Python实现中的性能微调使用列表而非字典如果元素是连续的整数索引0到N-1绝对使用列表list来实现parent和rank。列表的索引访问是O(1)且内存连续缓存友好速度远快于字典。只有在元素是字符串或其他不可哈希对象时才需要用字典建立映射。递归与迭代Python的递归有深度限制默认约1000和函数调用开销。对于超大规模数据N 10^5迭代版本的find可能更安全。但在算法题中N通常在10^4~10^5量级递归深度经过路径压缩后非常浅递归版本更简洁。内联函数调用在极度追求性能的场合如某些在线判题系统的压榨可以将find函数内联到union或is_connected中减少函数调用开销。但这会牺牲代码清晰度除非必要否则不推荐。6. 实战问题排查与调试技巧即使理解了原理在实战中也可能遇到各种奇怪的问题。下面是一些常见bug和调试方法。6.1 常见Bug清单初始化错误parent数组没有正确初始化为list(range(n))或者rank数组初始化为0应该是1。find函数忘记路径压缩写成了while parent[x] ! x: x parent[x]; return x。这种写法在多次查询后效率会急剧下降。union前未调用find直接比较parent[x]和parent[y]然后合并这是错误的因为parent[x]可能不是根节点。必须先找到根rootX find(x),rootY find(y)。合并了相同的根在union中如果发现rootX rootY应该直接返回否则会导致count错误减少甚至可能让rank错误增加。二维坐标映射错误在网格问题中id row * cols col是最常用的。写成row * rows col或col * rows row都是常见错误。count维护错误在__init__中count应初始化为n元素总数。在union中只有成功合并两个不同集合时才执行count - 1。6.2 调试方法可视化小规模数据当逻辑复杂或出现错误时最好的调试方法是用一个极小规模的例子比如5-10个元素手动模拟并查集的操作过程并打印出每次操作后的parent和rank数组。def debug_uf(uf): print(Parent:, uf.parent) print(Rank: , uf.rank) print(Count: , uf.count) # 打印每个集合 comps {} for i in range(len(uf.parent)): r uf.find(i) # 注意这里要调用find以看到路径压缩后的效果 comps.setdefault(r, []).append(i) print(Components:, comps) # 示例用法 uf UnionFind(5) debug_uf(uf) uf.union(0, 1) debug_uf(uf) uf.union(2, 3) debug_uf(uf) uf.union(1, 2) debug_uf(uf) print(Is 0 connected to 3?, uf.is_connected(0, 3))通过观察中间状态你可以清晰地看到路径压缩和按秩合并是如何工作的以及count是如何变化的从而快速定位逻辑错误。6.3 边界条件与输入验证元素索引从0开始我们的实现默认元素索引是0到N-1。如果题目给出的节点编号从1开始需要在传入并查集前减1或者在并查集内部处理偏移。非法输入在find和union中如果传入的索引x或y不在[0, n-1]范围内应该抛出异常或进行错误处理。在算法题中输入通常保证合法但在工程代码中需要谨慎。自连接union(x, x)应该被正确处理。我们的实现中find(x)会返回x的根rootX rootY成立所以会直接返回False不会进行无意义的合并也不会错误地减少count。这是符合预期的。并查集是一个“看似简单实则精妙”的数据结构。它的核心代码可能只有十几行但其中蕴含的优化思想路径压缩、按秩合并和摊还分析是算法设计中“以空间换时间”和“平摊复杂度”的典范。在Python中实现它让我们能够用非常简洁的代码解决一系列复杂的连通性问题。掌握它不仅能让你在算法面试中游刃有余更能提升你解决实际工程中分组、聚类、动态连接等问题的思维能力。下次当你遇到需要维护动态关系的问题时不妨先想一想这个问题能用并查集优雅地解决吗