1. 并查集解决连通性问题的瑞士军刀第一次听说并查集Disjoint Set Union简称DSU是在解决LeetCode第547题朋友圈的时候。当时用DFS解法总感觉代码写得太啰嗦直到发现评论区有人用不到20行代码就搞定了问题——那是我与这个神奇数据结构的初次相遇。简单来说并查集就是专门处理动态连通性问题的数据结构。想象你有一堆散落的节点需要频繁回答节点A和节点B是否相连这样的问题这时候普通的遍历方法效率太低而并查集可以在近乎常数时间内完成查询和合并操作。它的核心操作只有两个Find查找某个元素属于哪个集合就像查快递包裹最后到了哪个配送站Union合并两个不相交的集合像把两个快递网点合并成一个实际项目中我经常用它处理社交网络的好友关系、电路连接检查、游戏中的像素连通区域计算等问题。特别是在处理百万级节点的图数据时传统DFS/BFS可能直接栈溢出而经过优化的并查集依然能稳定运行。2. 并查集的实现与优化技巧2.1 基础版实现数组与森林表示我们先来看最朴素的实现方式。假设有5个节点0-4初始时每个节点自成一个集合class DSU: def __init__(self, n): self.parent list(range(n)) # 每个节点的父节点初始为自己 def find(self, x): while self.parent[x] ! x: x self.parent[x] return x def union(self, x, y): rootX self.find(x) rootY self.find(y) if rootX ! rootY: self.parent[rootY] rootX这个版本虽然直观但存在明显缺陷。当进行多次union操作后树可能退化成链表使得find操作的时间复杂度恶化到O(n)。我在第一次实现时就踩过这个坑——当处理10万个节点的数据时程序运行了整整两分钟。2.2 路径压缩把树拍扁的技巧路径压缩就像把家族族谱扁平化处理。当我们查找某个节点的根时顺带把沿途所有节点的父节点直接指向根节点def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) # 递归压缩 return self.parent[x]这个优化让后续查询变得更快。实测在LeetCode 200题岛屿数量中使用路径压缩后运行时间从68ms降到了40ms。不过要注意递归写法可能引发栈溢出对于特别大的数据集可以用迭代版本def find(self, x): root x while self.parent[root] ! root: root self.parent[root] while x ! root: # 二次遍历进行压缩 next_node self.parent[x] self.parent[x] root x next_node return root2.3 按秩合并保持树的平衡另一个重要优化是按秩合并Union by Rank。我们额外维护一个rank数组记录树的深度总是将较浅的树合并到较深的树下class DSU: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n def union(self, x, y): rootX self.find(x) rootY self.find(y) if rootX rootY: return if self.rank[rootX] self.rank[rootY]: self.parent[rootY] rootX else: self.parent[rootX] rootY if self.rank[rootX] self.rank[rootY]: self.rank[rootY] 1这两个优化配合使用能使单次操作的时间复杂度降到接近O(1)。我在处理社交网络数据时对比发现优化后的并查集比普通BFS快了近百倍。3. LeetCode经典题目实战解析3.1 朋友圈问题LeetCode 547题目描述给定n*n的矩阵M表示朋友关系M[i][j]1表示第i和第j个学生是朋友直接或间接。求有多少个朋友圈。这是最典型的并查集应用题。我的解题思路是初始化n个独立学生遍历矩阵对每个M[i][j]1的关系执行union(i,j)最后统计有多少个不同的根节点def findCircleNum(M): 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)})有个容易忽略的细节矩阵是对称的所以只需要遍历右上三角部分。这个优化让运行时间又减少了30%。3.2 账户合并LeetCode 721更复杂的应用场景出现在这道题给定一组账户信息其中每个账户包含多个邮箱需要将有相同邮箱的账户合并。我的建模方法是将每个邮箱映射到一个账户ID当发现邮箱已存在时执行union操作最后整理合并结果def accountsMerge(accounts): dsu DSU(len(accounts)) email_to_id {} # 第一遍建立邮箱到账户ID的映射并合并 for i, account in enumerate(accounts): for email in account[1:]: if email in email_to_id: dsu.union(i, email_to_id[email]) else: email_to_id[email] i # 第二遍整理合并结果 id_to_emails defaultdict(set) for email, id_ in email_to_id.items(): root dsu.find(id_) id_to_emails[root].add(email) return [[accounts[i][0]] sorted(emails) for i, emails in id_to_emails.items()]这个案例展示了如何将现实问题抽象为连通性问题。我最初尝试用哈希表直接记录关系结果发现处理交叉引用时非常麻烦转而使用并查集后代码简洁了许多。4. 高级应用与变种问题4.1 带权并查集处理关系型问题有些问题不仅需要知道是否连通还需要知道节点间的具体关系。比如LeetCode 399除法求值问题需要处理变量间的比值关系。解决方案是给边赋予权重class WeightedDSU: def __init__(self, n): self.parent list(range(n)) self.weight [1.0] * n def find(self, x): if self.parent[x] ! x: origin_parent self.parent[x] self.parent[x] self.find(self.parent[x]) self.weight[x] * self.weight[origin_parent] return self.parent[x] def union(self, x, y, value): rootX self.find(x) rootY self.find(y) if rootX rootY: return self.parent[rootX] rootY self.weight[rootX] self.weight[y] * value / self.weight[x]这种带权并查集在解决等式关系、图论中的距离问题时非常有用。我在一次数据一致性检查的任务中就应用了这个技巧成功找出了存在矛盾的数据记录。4.2 动态连通性与离线查询有些问题需要处理动态变化的连通性状态比如LeetCode 1697检查边长度限制的路径是否存在。这类问题通常需要对查询按特定条件排序按顺序处理边和查询def distanceLimitedPathsExist(n, edgeList, queries): edgeList.sort(keylambda x: x[2]) queries sorted([(q[0], q[1], q[2], i) for i, q in enumerate(queries)], keylambda x: x[2]) dsu DSU(n) res [False] * len(queries) edge_ptr 0 for q in queries: while edge_ptr len(edgeList) and edgeList[edge_ptr][2] q[2]: dsu.union(edgeList[edge_ptr][0], edgeList[edge_ptr][1]) edge_ptr 1 res[q[3]] dsu.find(q[0]) dsu.find(q[1]) return res这种离线处理技巧在数据库查询优化、网络路由等场景都有应用。我在处理用户行为日志分析时就借鉴了这个思路将实时查询转化为批量处理性能提升了5倍以上。