1. 项目概述为什么并查集是算法工程师的“瑞士军刀”如果你刷过LeetCode或者参与过一些需要处理分组、连通性问题的项目大概率会碰到“并查集”这个数据结构。我第一次接触它是在解决一个社交网络的好友推荐问题当时需要快速判断两个用户是否属于同一个圈子比如都关注了某个话题。用传统的遍历方法数据量一大就慢得不行直到我用了并查集性能直接提升了好几个数量级。从那以后它就成了我解决一类特定问题的首选工具。简单来说并查集是一种用于管理元素分组情况的数据结构它高效地支持两种操作“并”Union合并两个元素所在的集合和“查”Find查询某个元素属于哪个集合。它的核心思想非常巧妙用树形结构来代表集合并通过路径压缩和按秩合并等优化技巧使得这两种操作的平均时间复杂度接近常数级O(α(n))其中α(n)是增长极慢的反阿克曼函数。这意味着对于实际应用中的任何规模数据你都可以认为它的操作是瞬间完成的。这篇总结就是把我这些年用Python实现并查集、用它解决各种实际问题的经验系统地梳理出来。无论你是正在准备算法面试的新手还是需要在项目中处理图论、动态连通性问题的开发者这篇文章都能给你一套可以直接“抄作业”的代码模板和清晰的解题思路。我们会从最基础的原理讲起一步步拆解优化技巧最后用几个经典的LeetCode题目和一个小型项目场景带你彻底掌握这把算法“瑞士军刀”。2. 并查集核心原理与Python实现拆解2.1 数据结构设计从数组到森林的映射并查集最直观的实现方式是使用一个数组在Python中就是列表。数组的索引代表每个元素通常我们给每个元素分配一个唯一的ID这个ID就是索引而数组的值代表这个元素的“父节点”。初始化时每个元素都自成一派所以它的父节点就是它自己。class UnionFind: def __init__(self, n): # 初始化每个元素的父节点指向自己 self.parent list(range(n)) # 可选记录每棵树的“秩”高度或大小用于优化合并 self.rank [0] * n # 按高度合并 # self.size [1] * n # 按大小合并这里有几个关键点需要理解。parent列表是并查集的核心。parent[i] j表示元素i的父节点是j。当parent[i] i时说明i就是它所在集合的“根节点”或“代表元”。一个集合就是由同一个根节点连接起来的所有元素。为什么用数组而不用字典对于元素ID是连续整数的情况数组的访问效率O(1)是最高的内存也紧凑。如果你的元素是字符串或其他对象可以先建立一个从元素到唯一整数ID的映射再用数组实现并查集逻辑。rank列表是优化合并操作的关键。它的含义是“树高的上界”。初始化时每个单独的元素都是一棵高度为0的树。我们也可以选择记录size集合的大小两种优化策略按秩合并的目的都是避免在合并时让树变得不平衡从而保证后续查找的效率。2.2 “查”操作路径压缩的魔法“查”操作的目的是找到某个元素所在集合的根节点。最朴素的方法是沿着父节点指针一路向上找直到找到根节点。def find_naive(self, x): while self.parent[x] ! x: x self.parent[x] return x这个方法的问题是如果树变得很高比如一条链每次查找的时间复杂度就是O(n)。想象一下如果每次合并都把新树挂到老树的根节点下很容易形成一条长链。路径压缩优化就是为了解决这个问题。它的思想非常直接既然我这次费劲找到了根节点为什么不直接把沿途所有节点的父节点都指向根呢这样下次再查找这些节点时一步就能到位。def find(self, x): # 方法一递归实现代码简洁但可能有递归深度限制 # if self.parent[x] ! x: # self.parent[x] self.find(self.parent[x]) # 递归压缩 # return self.parent[x] # 方法二迭代实现更通用 root x # 第一步找到根节点root while self.parent[root] ! root: root self.parent[root] # 第二步从x开始向上遍历将路径上所有节点的父节点直接设为root while self.parent[x] ! root: parent self.parent[x] self.parent[x] root x parent return root实操心得我强烈推荐使用迭代法实现路径压缩。虽然递归写法更简洁但在Python中对于深度很大的树虽然优化后很难出现有递归深度限制的风险。迭代写法则完全避免了这个问题并且效率上几乎没有差别。在算法竞赛或工程中迭代法是更稳妥的选择。路径压缩后并查集操作的均摊时间复杂度就变得极低。可以这样理解第一次查找一个深层节点可能需要O(log n)但这次查找同时“压平”了路径使得该节点及其所有祖先的下次查找都变成O(1)。2.3 “并”操作按秩合并的艺术“并”操作的目的是将两个元素所在的集合合并成一个。首先我们需要找到它们各自的根节点root_x和root_y。如果根节点相同说明它们本来就在一个集合里无需操作。如果不同就需要合并。如何合并最简单的办法是把root_x的父节点设为root_y或者反过来。但随意的合并可能导致树的高度增加。例如总是把大树挂到小树上新树的高度就是原大树高度1这可能会让树越来越高。按秩合并就是为了控制树的高度。我们有两种“秩”的定义按高度合并rank记录树高的上界。合并时总是将矮树的根挂到高树的根上。如果两棵树一样高则任选一个作为根并将新根的高度加1。按大小合并size记录集合的元素个数。合并时总是将小集合的根挂到大集合的根上并更新大集合的大小。两种方法都能有效控制树高使树保持近似平衡。通常按高度合并更直观。def union(self, x, y): root_x self.find(x) root_y self.find(y) if root_x root_y: return # 已在同一集合无需合并 # 按秩高度合并 if self.rank[root_x] self.rank[root_y]: # 将较矮的树root_x挂到较高的树root_y下 self.parent[root_x] root_y elif self.rank[root_x] self.rank[root_y]: self.parent[root_y] root_x else: # 两棵树一样高任选一个作为根并增加其高度 self.parent[root_y] root_x self.rank[root_x] 1 # 如果使用按大小合并代码如下 # 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]注意事项find操作在union中会被调用。这意味着在合并的同时路径压缩优化也会生效。所以一次union操作不仅连接了两个集合还可能顺带压平了从x和y到各自根节点的路径。这是并查集高效的关键优化是连锁反应的。2.4 完整模板与辅助方法将以上部分组合起来我们就得到了一个带有路径压缩和按秩合并的完整并查集模板。此外我们通常还会增加一些有用的辅助方法。class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n # 可选记录连通分量数量 self.count n def find(self, x): # 迭代路径压缩 root x while self.parent[root] ! root: root self.parent[root] while self.parent[x] ! root: parent self.parent[x] self.parent[x] root x parent return root def union(self, x, y): 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: self.parent[root_y] root_x self.rank[root_x] 1 self.count - 1 # 合并成功连通分量减1 return True # 合并成功 def connected(self, x, y): 判断x和y是否连通 return self.find(x) self.find(y) def get_count(self): 返回当前连通分量的数量 return self.count这个模板已经非常实用了。count变量用于动态跟踪当前有多少个独立的集合连通分量在解决一些问题时非常方便比如判断最终图是否完全连通。3. 并查集经典应用场景与解题套路掌握了模板我们来看看并查集到底能解决哪些问题。其核心应用场景都围绕着“动态连通性”。3.1 场景一判断图中节点是否连通这是最直接的应用。给定一个无向图可能以边列表的形式给出我们需要回答多次查询“节点A和节点B是否相连”如果使用DFS/BFS每次查询都需要遍历代价高昂。并查集可以在构建图的过程中就预处理好连通关系使得每次查询接近O(1)。解题套路初始化一个大小为节点数的并查集。遍历所有的边对每条边连接的两个节点执行union操作。对于任何查询(u, v)调用connected(u, v)即可得到结果。LeetCode例题547. 省份数量 或称朋友圈问题 题目本质是求无向图中连通分量的个数。直接套用上述套路遍历邻接矩阵或列表合并所有直接相连的城市最后并查集中count的值就是省份数量。3.2 场景二检测图中是否有环在无向图中对于一条新边(u, v)如果u和v在连接前就已经在同一个集合里了那么添加这条边必然会产生环。这个性质让并查集成为判断无向图是否有环的高效工具复杂度几乎是O(n)。解题套路初始化并查集。遍历每条边(u, v)如果find(u) find(v)说明u和v已连通当前边会导致环返回True。否则执行union(u, v)。遍历结束未发现环则返回False。LeetCode例题684. 冗余连接 题目要求找出使得无向树本应无环形成环的那条边。完美契合上述套路从前往后遍历边第一条导致find(u) find(v)的边就是答案。3.3 场景三处理“岛屿”类网格问题很多网格问题可以被转化为图论问题。例如一个二维网格‘1’代表陆地‘0’代表水相邻上下左右的陆地可以连通。求岛屿数量。我们可以把每个陆地单元格看作一个节点相邻关系看作边。解题套路初始化并查集大小为网格单元格总数m * n。但只初始化那些是陆地的单元格不更常见的做法是初始化所有格子但只对陆地格子进行连接操作。或者使用“虚拟节点”技巧。遍历网格对于每个陆地单元格查看其右方和下方的邻居避免重复连接。如果邻居也是陆地则将当前单元格与邻居单元格在并查集中union。这里需要将二维坐标(i, j)映射到一维IDid i * n j。遍历完成后统计有多少个独立的陆地集合即根节点是自身且对应格子是陆地的数量就是岛屿数量。避坑技巧在网格问题中只检查右方和下方邻居可以避免重复连接。因为union(a, b)和union(b, a)是等价的如果检查四个方向每条边会被处理两次。同时这种遍历顺序也保证了不会漏掉任何连接。3.4 场景四等式方程的可满足性这类问题将变量之间的相等/不等关系作为约束判断所有约束是否能被同时满足。并查集天然适合处理“相等”关系的传递性。解题套路遍历所有“相等”约束如ab将约束两端的变量进行union操作。这样所有相等的变量都会在同一个集合里。遍历所有“不等”约束如a!b。如果find(a) find(b)说明根据之前的相等关系a和b必须相等这与当前的不等约束矛盾。返回False。所有不等约束检查完毕都无矛盾返回True。LeetCode例题990. 等式方程的可满足性 直接应用上述套路即可。关键在于第一步先处理所有等式建立连通关系第二步再用这些关系去验证不等式是否矛盾。4. 高级技巧与性能优化实战4.1 按秩合并与路径压缩的协同效应我们之前分别介绍了路径压缩和按秩合并。当它们一起使用时会产生“112”的效果。路径压缩会改变树的高度这会不会破坏rank记录的高度信息呢实际上rank在优化后的并查集中不再精确表示树的高度而是一个“上界”或“秩”。路径压缩可能会使树的高度变小但rank值我们只会在合并时进行比较和更新。一个被压缩过的树其rank值可能比实际高度大但这并不影响合并决策的正确性。因为合并时我们比较的是两个根节点的rank即使这个值比实际高度大也只是让我们在合并时更“保守”一点可能将实际矮一点的树判断为同高这并不会导致错误只是可能错过一次更优的合并对整体效率影响微乎其微。两者的结合被证明能达到近乎最优的摊还时间复杂度。4.2 处理非连续ID与动态扩容我们的模板假设元素ID是0到n-1的连续整数。如果元素是字符串、对象或者ID不连续怎么办方案一双射字典最通用的方法是维护两个字典。class UnionFindGeneric: def __init__(self): self.parent {} self.rank {} def find(self, x): # 如果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): root_x self.find(x) root_y self.find(y) if root_x root_y: return # ... 按秩合并逻辑这种方法非常灵活支持任何可哈希的元素类型。缺点是字典操作的开销比数组稍大。方案二映射到连续ID如果元素总量已知或可预估可以先遍历所有元素为每个唯一元素分配一个连续的整数ID建立一个element - id的映射字典。然后用这个ID去操作基于数组的标准并查集。查询时再通过id - element的反向映射找回元素。这在处理一批已知数据时很高效。4.3 维护集合的附加信息有时我们不仅需要知道元素是否连通还需要知道集合的某些属性比如集合的大小、集合内所有元素的和、最大值等。我们可以在并查集的基础上增加额外的数组来维护这些信息并在union操作时同步更新。例如要维护每个集合的大小def __init__(self, n): self.parent list(range(n)) self.size [1] * n # 每个集合的初始大小都是1 def union(self, x, y): root_x self.find(x) root_y 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 self.parent[root_y] root_x self.size[root_x] self.size[root_y] # 更新大小这样get_size(x)可以通过self.size[self.find(x)]获得。LeetCode例题128. 最长连续序列 这道题可以用哈希集合做但用并查集也很巧妙。将数组中的每个数看作一个节点如果存在相邻的数num和num1同时存在就将它们union起来。同时维护每个集合的大小。最终最大的集合大小就是答案。这里就需要用到维护集合大小的技巧。4.4 带权并查集这是并查集更高级的用法每个节点到其父节点不仅有关联还有一个“权值”。这个权值可以表示距离、差值、关系类型等。在find进行路径压缩时需要同时更新权值在union时需要根据关系推导出两个根节点之间应有的权值。一个经典应用是解决“食物链”或“判断语句矛盾”类问题。例如知道A和B的关系、B和C的关系推导A和C的关系。带权并查集通过维护节点到根节点的相对关系来实现。由于实现较为复杂这里给出一个解决“等式方程的可满足性”的带权并查集思路虽然用普通并查集更简单我们可以定义权值0表示与根节点同类1表示不同类。在union时根据等式或不等式来推算权值。这属于并查集的进阶内容在掌握了基础后值得深入研究。5. 常见问题排查与性能调优实录在实际编码和解题中你可能会遇到下面这些问题。5.1 问题一为什么我的并查集跑得慢可能原因及排查没有进行优化使用了最朴素的find无路径压缩和随意union。这是性能杀手。务必使用“路径压缩按秩合并”的模板。在循环内错误调用find# 错误示例在需要多次判断连通性时每次都find for i in range(n): for j in range(i1, n): if uf.find(i) uf.find(j): # 这里每次都会进行find操作 do_something()如果do_something()里不改变并查集结构那么uf.find(i)的结果在循环内是不变的却每次都被计算。对于需要频繁判断的情况可以预先计算好根节点。# 优化预先计算所有元素的根 roots [uf.find(i) for i in range(n)] for i in range(n): for j in range(i1, n): if roots[i] roots[j]: # 直接比较省去find开销 do_something()使用了递归版本的路径压缩导致递归过深虽然经过路径压缩后树很扁平但理论上存在极端情况。改用迭代版本更安全。5.2 问题二如何处理大规模数据下的内存问题标准并查集需要O(n)的数组空间对于元素数量n极大的情况例如十亿级别内存可能成为瓶颈。优化思路使用字典的惰性初始化如前所述的UnionFindGeneric类只在元素首次出现时才在字典中分配条目。这对于元素稀疏的场景非常有效。使用数组但分块处理如果数据可以分批次处理且批次间关联不大可以考虑对每个批次单独使用一个并查集最后再合并结果。这需要具体问题具体分析。考虑使用其他数据结构对于纯粹的连通性查询如果离线所有边先给齐再回答所有查询有时可以使用Tarjan的离线LCA算法。但对于动态连接、在线查询的场景并查集的空间复杂度O(n)通常是最优的之一。5.3 问题三并查集初始化大小n如何确定这是一个常见的困惑点。n应该是所有可能出现的、需要被放入并查集进行关联的元素的总数。在网格问题中n 行数 * 列数因为每个格子都可能是一个元素。在等式方程问题中n 26如果只有小写字母或者使用字典动态扩容。在社交网络问题中n 用户总数。如果无法提前知道n就使用基于字典的动态版本。如果知道最大可能ID可以按最大值初始化即使有些ID没出现也只是浪费少量空间但保证了正确性。5.4 问题四union操作时到底应该按rank合并还是按size合并两者在理论上的时间复杂度级别是一样的都能保证树高为O(log n)。细微差别在于按rank高度合并更直接地控制树高是教科书和算法竞赛中最常见的写法。按size大小合并有时更方便因为集合大小本身可能就是我们需要的答案如求最大连通分量大小。选择哪一种取决于你的需求。在我的经验里两者在实际性能上差异极小选择你习惯的一种并保持一致即可。5.5 问题五并查集能否处理有向图标准的并查集是为无向图设计的它维护的是一种等价关系自反、对称、传递。有向图中的连通性强连通分量通常用Kosaraju或Tarjan算法来解决。但是有一种特殊的有向图问题可以用并查集的变种——“带权并查集”来解决例如前面提到的关系推导问题A是B的父亲B是C的父亲问A和C的关系。这里的“边”带有方向/类型信息并查集维护的是元素之间的相对关系。6. 从算法到项目一个简易社交网络好友推荐模拟为了把知识串联起来我们设计一个简化版的社交网络好友推荐场景。假设我们有一个用户系统用户可以关注话题。当两个用户关注了同一个话题我们就认为他们之间存在一种“潜在关联”。我们的目标是给定一个用户找出与他“间接关联”最紧密的用户即通过共同关注话题形成的连通分量中除了自己以外的其他用户作为潜在的好友推荐。数据表示users: 用户ID列表例如[0, 1, 2, 3, 4]topics: 话题ID列表例如[100, 101, 102]user_topic_map: 字典记录每个用户关注的话题列表例如{0: [100, 101], 1: [101], 2: [102], 3: [100, 102], 4: [101]}思路与实现建立关联如果两个用户关注了同一个话题他们就应该被连接起来。但直接遍历用户两两对比效率是O(n²)。更高效的方法是遍历话题将关注了同一话题的所有用户两两连接。使用并查集初始化一个并查集大小为用户数量。遍历每个话题的关注者列表将该话题下的所有用户进行union操作。生成推荐对于目标用户target_user首先找到他所在的集合根节点root。然后遍历所有用户找出那些根节点也是root的用户这些用户就是与他间接关联的用户从中排除自己即可作为推荐列表。class SocialNetworkRecommender: def __init__(self, user_count, user_topic_map): 初始化推荐器 :param user_count: 用户总数 :param user_topic_map: 字典{user_id: [topic_id1, topic_id2, ...]} self.uf UnionFind(user_count) self._build_connections(user_topic_map) def _build_connections(self, user_topic_map): 根据用户-话题映射构建用户间的连通关系 # 反转映射从话题到关注该话题的用户列表 topic_to_users {} for user_id, topics in user_topic_map.items(): for topic in topics: topic_to_users.setdefault(topic, []).append(user_id) # 对每个话题将其下的所有用户两两连接 for users in topic_to_users.values(): if len(users) 1: first_user users[0] for other_user in users[1:]: self.uf.union(first_user, other_user) def recommend_friends(self, target_user): 为目标用户推荐好友同属一个关注话题圈子的其他用户 root self.uf.find(target_user) recommendations [] for user in range(self.uf.count): # 假设用户ID从0到user_count-1 if user ! target_user and self.uf.find(user) root: recommendations.append(user) return recommendations # 模拟数据 user_count 5 user_topic_map { 0: [100, 101], 1: [101], 2: [102], 3: [100, 102], 4: [101] } recommender SocialNetworkRecommender(user_count, user_topic_map) print(f用户0的推荐好友: {recommender.recommend_friends(0)}) # 输出: [1, 4] (因为都关注了话题101) print(f用户2的推荐好友: {recommender.recommend_friends(2)}) # 输出: [3] (因为都关注了话题102)这个例子展示了并查集如何将“多对多”的关系用户-话题高效地聚合为“一对多”的连通分量从而快速实现群体发现。在实际工程中数据量巨大这种基于连通性的预处理可以极大加速后续的查询和推荐计算。并查集的魅力在于它用如此简单的结构一个数组和巧妙的优化路径压缩、按秩合并解决了看似复杂的关系维护问题。我个人的体会是在遇到需要处理分组、连通、传递关系的问题时第一时间考虑并查集往往能带来意想不到的简洁和高效。把它练熟形成肌肉记忆你的算法工具箱里就又多了一件趁手的利器。最后一个小技巧在参加编程比赛时我通常会把并查集模板预先写在代码开头它就像一把万能钥匙随时准备解开那些关于“连接”的谜题。