别再死记硬背了！用Python实现并查集（DSU）搞定朋友圈、合并账户这些LeetCode题

用Python玩转并查集从朋友圈算法到账户合并实战在准备算法面试时很多开发者都会遇到这样的困境明明理解了某个数据结构的理论却在LeetCode题目中不知如何应用。并查集Disjoint Set Union, DSU就是这样一个典型的理论易懂实战难用的数据结构。本文将带你从实际问题出发通过Python代码实现掌握并查集在算法题中的灵活运用。1. 为什么并查集是算法面试的隐藏王牌并查集是一种高效处理不相交集合合并与查询操作的数据结构。它的核心价值在于接近常数时间的操作效率经过优化的并查集单次操作时间复杂度接近O(1)简洁优雅的实现基础版本只需不到20行Python代码广泛的适用场景从社交网络关系到图像处理都有应用典型应用场景社交网络中的朋友关系如LeetCode 547账户合并问题如LeetCode 721连续序列检测如LeetCode 128图的连通性维护如LeetCode 1579# 最简并查集实现非优化版 class DSU: def __init__(self, n): self.parent list(range(n)) def find(self, x): if self.parent[x] ! x: return self.find(self.parent[x]) return x def union(self, x, y): self.parent[self.find(x)] self.find(y)这个基础版本虽然简单但已经能够解决许多问题。接下来我们会看到如何在此基础上进行优化。2. 并查集的核心路径压缩与按秩合并要让并查集真正高效需要理解两种关键优化技术2.1 路径压缩扁平化树结构路径压缩通过在查找过程中直接将被查找节点连接到根节点显著减少后续查找时间。def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) # 路径压缩关键行 return self.parent[x]效果对比操作类型未优化时间复杂度路径压缩后查找O(log n)O(α(n))合并O(log n)O(α(n))注α(n)是反阿克曼函数增长极其缓慢通常视为常数2.2 按秩合并保持树的平衡按秩合并通过记录树的深度总是将较浅的树合并到较深的树下避免退化成链表。class DSU: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n # 记录树的高度 def union(self, x, y): xroot self.find(x) yroot self.find(y) if xroot yroot: return # 按秩合并关键逻辑 if self.rank[xroot] self.rank[yroot]: self.parent[xroot] yroot else: self.parent[yroot] xroot if self.rank[xroot] self.rank[yroot]: self.rank[xroot] 13. 实战解析LeetCode 547朋友圈问题让我们用优化后的并查集来解决经典的LeetCode 547题。题目给定一个N×N的矩阵M表示朋友关系M[i][j]1表示第i个人和第j个人是朋友求有多少个朋友圈。解题步骤初始化并查集每个人最初是自己的父节点遍历矩阵合并所有直接朋友关系统计不同根节点的数量class Solution: def findCircleNum(self, M: List[List[int]]) - int: n len(M) dsu DSU(n) for i in range(n): for j in range(i1, n): # 利用对称性只需遍历上半矩阵 if M[i][j] 1: dsu.union(i, j) # 统计不同根节点数量 return len({dsu.find(i) for i in range(n)})性能分析时间复杂度O(n² α(n))其中α(n)是反阿克曼函数空间复杂度O(n)用于存储父节点和秩数组4. 进阶应用LeetCode 721账户合并账户合并问题比朋友圈更复杂需要处理字符串类型的账户名而非简单的数字索引。题目给定一组账户每个账户包含用户名和多个邮箱地址需要将属于同一人的账户合并。解题思路建立邮箱到账户名的映射使用并查集合并有相同邮箱的账户最后按合并结果整理输出class DSU: def __init__(self): self.parent {} def find(self, x): if x not in self.parent: self.parent[x] x if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): self.parent[self.find(x)] self.find(y) class Solution: def accountsMerge(self, accounts: List[List[str]]) - List[List[str]]: dsu DSU() email_to_name {} # 建立邮箱到姓名的映射和并查集关系 for acc in accounts: name acc[0] for email in acc[1:]: email_to_name[email] name dsu.union(acc[1], email) # 用第一个邮箱作为代表 # 按根邮箱分组 merged defaultdict(list) for email in email_to_name: merged[dsu.find(email)].append(email) # 整理输出结果 return [[email_to_name[key]] sorted(emails) for key, emails in merged.items()]关键技巧使用字典而非数组实现并查集适应字符串键选择每个账户的第一个邮箱作为代表元素最后对合并后的邮箱列表进行排序5. 并查集的特殊应用LeetCode 128最长连续序列这道题要求找出未排序数组中最长的连续数字序列的长度。使用并查集的解法相当巧妙将每个数字视为一个独立集合对于每个数字n检查n-1和n1是否存在如果存在则合并集合最后统计最大集合的大小class DSU: def __init__(self): self.parent {} self.size {} # 记录集合大小 def find(self, x): if x not in self.parent: return None if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): xroot self.find(x) yroot self.find(y) if xroot is None or yroot is None or xroot yroot: return # 按大小合并小集合并入大集合 if self.size[xroot] self.size[yroot]: xroot, yroot yroot, xroot self.parent[yroot] xroot self.size[xroot] self.size[yroot] def add(self, x): if x not in self.parent: self.parent[x] x self.size[x] 1 class Solution: def longestConsecutive(self, nums: List[int]) - int: if not nums: return 0 dsu DSU() nums set(nums) # 去重 for num in nums: dsu.add(num) dsu.union(num, num - 1) dsu.union(num, num 1) return max(dsu.size.values())优化点使用集合去重避免重复处理维护集合大小信息避免最后再统计按大小合并保持树结构平衡6. 并查集在图连通性问题中的应用LeetCode 1579这道题要求我们删除尽可能多的边同时保持图的完全可遍历性。使用并查集的解题思路优先处理双向边类型3然后分别处理Alice和Bob的专属边统计可以删除的冗余边数量class DSU: def __init__(self, n): self.parent list(range(n1)) # 节点从1开始编号 self.rank [0] * (n1) 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): xroot self.find(x) yroot self.find(y) if xroot yroot: return False # 已经连通边可删除 if self.rank[xroot] self.rank[yroot]: xroot, yroot yroot, xroot self.parent[yroot] xroot if self.rank[xroot] self.rank[yroot]: self.rank[xroot] 1 return True # 成功合并边需保留 class Solution: def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) - int: # 分别处理三种类型的边 alice_edges [] bob_edges [] common_edges [] for t, u, v in edges: if t 1: alice_edges.append((u, v)) elif t 2: bob_edges.append((u, v)) else: common_edges.append((u, v)) # 处理公共边 dsu DSU(n) common_used 0 for u, v in common_edges: if dsu.union(u, v): common_used 1 # 检查Alice的连通性 alice_dsu copy.deepcopy(dsu) alice_used 0 for u, v in alice_edges: if alice_dsu.union(u, v): alice_used 1 if common_used alice_used ! n - 1: return -1 # 检查Bob的连通性 bob_dsu copy.deepcopy(dsu) bob_used 0 for u, v in bob_edges: if bob_dsu.union(u, v): bob_used 1 if common_used bob_used ! n - 1: return -1 # 计算可删除的边数 return len(edges) - (common_used alice_used bob_used)关键点优先处理类型3的边因为它们对双方都有用使用深拷贝创建独立的并查集实例确保最终保留的边数正好是n-1生成树在实际刷题过程中我发现并查集的应用远不止这些。比如在图像处理中可以用来做连通区域标记在游戏开发中可以用来管理物体的碰撞关系。掌握并查集的核心思想和优化技巧能让你在面对这类问题时游刃有余。