你有没有遇到过这样的场景一个看似简单的“分组”问题却因为数据量巨大、关系动态变化导致用数组、哈希表甚至图论都写得异常复杂性能还上不去比如社交网络里判断两个人是否属于同一个朋友圈或者游戏里判断两个像素点是否连通又或者编译器里判断两个变量名是否指向同一个内存地址。这类问题的核心其实就一句话高效地管理一组动态变化的、具有“归属”关系的元素集合。你需要的不是一个复杂的算法而是一个能直接抓住问题本质的“数据结构思维”。今天要聊的并查集就是为这类问题而生的。很多人第一次接触并查集会觉得它很“玄学”——几个数组操作怎么就解决了这么复杂的问题它的名字Union-Find也透着一种抽象感。这篇文章我们不打算从枯燥的定义开始。我想带你从一次真实的“踩坑”体验出发看看为什么常规思路会失效然后一步步拆解并查集的核心思想最后深入到两种最经典的实现——QuickFind 和 QuickUnion 的源码层面理解它们为何一个“快查”一个“快并”以及如何根据你的场景做出选择。你会发现并查集真正强大的地方不在于它有多高深而在于它用极简的抽象解决了工程中一大类“关系维护”的痛点。1. 从一次“分组”需求崩溃看并查集要解决的核心问题假设你正在处理一个用户关系系统。最初你有 10 个用户编号 0 到 9他们互不相识。随着时间推移用户之间会建立“好友”关系。你的系统需要频繁回答一个问题“用户A和用户B目前是否在同一个社交圈即通过好友关系间接连通”第一反应用数组或列表记录分组。你可能会创建一个数组group[]group[i]表示用户i所属的组号。初始时group [0,1,2,3,4,5,6,7,8,9]每人自成一组。 当用户 1 和用户 2 成为好友你需要合并他们所在的组。于是你遍历整个数组把所有group[i] 2的项都改成group[i] 1或者反过来。一次合并操作时间复杂度是 O(N)。 这还没完。用户 2 又和用户 3 成为好友。现在你需要合并组1包含用户1,2和组3。你又得遍历数组找出所有属于组3的用户把他们归到组1。随着合并越来越多组号会变得混乱合并操作的成本始终是 O(N)。第二反应用邻接表建图然后用 BFS/DFS 判断连通性。这确实能准确判断任意两点是否连通。但是每次查询“用户A和用户B是否连通”你都需要从A点出发做一次图遍历BFS/DFS时间复杂度是 O(NE)在最坏情况下接近 O(N^2)。对于需要每秒处理成千上万次查询的系统这是不可接受的。这时并查集的价值就凸显出来了。它专门为这种场景设计动态连通性关系边是逐步添加的不是一开始就给定的静态图。高效查询需要极快地回答“两个元素是否属于同一集合”。高效合并需要将两个集合合并成一个。并查集的核心 API 只有两个find(x): 查找元素x属于哪个集合通常返回集合的“代表元”。union(x, y): 将元素x和y所在的集合合并。它的目标就是让这两个操作的平均时间复杂度接近常数级 O(α(n))其中 α(n) 是增长极慢的反阿克曼函数对于任何实际应用中的 n其值不会超过 5。并查集真正解决的不是“如何表示关系”而是“如何用最小的维护成本支撑海量的动态关系查询”。2. 理解并查集的“森林”隐喻与两种核心操作并查集最巧妙的抽象是将集合表示为“树”或“森林”。每个集合是一棵树树根就是该集合的“代表元”。判断两个元素是否属于同一集合就等价于判断它们的树根是否相同。初始时每个元素都是一棵独立的树只有根节点。我们用数组parent[]来表示这个森林。parent[i]存储元素i的父节点。如果i是根节点一种常见的做法是令parent[i] i自环或者parent[i] -1。基于这个“森林”模型我们来看两种最基础的实现策略它们分别代表了在find查和union并之间的不同权衡。2.1 QuickFind为了“查得快”牺牲“并”的效率QuickFind 的思路非常直接让同一个集合里的所有元素都直接指向同一个“代表元”根节点。这样find(x)操作只需要一次数组访问parent[x]时间复杂度是严格的 O(1)。我们来看看它的源码实现逻辑。假设有 N 个元素0 到 N-1class QuickFindUF: def __init__(self, n): # 初始化每个元素的id即集合代表元就是自己 self.id list(range(n)) def find(self, p): # 查找直接返回元素p的集合id return self.id[p] def connected(self, p, q): # 判断连通性比较两个元素的集合id是否相同 return self.find(p) self.find(q) def union(self, p, q): # 合并操作这是QuickFind的关键也是其瓶颈所在 pid self.find(p) qid self.find(q) if pid qid: return # 已经在同一集合无需操作 # 将属于pid集合的所有元素全部改为属于qid集合 for i in range(len(self.id)): if self.id[i] pid: self.id[i] qid关键点分析find为什么快因为它只是self.id[p]一次数组访问。这就是“QuickFind”名字的由来。union为什么慢因为它需要遍历整个数组for i in range(len(self.id))将所有属于pid集合的元素id[i]修改为qid。一次union操作的时间复杂度是 O(N)。适用场景如果你的应用特点是find查询操作极其频繁而union合并操作非常少那么 QuickFind 可能是合适的。但在绝大多数动态连通性问题中合并操作和查询操作是交错发生的O(N) 的合并成本是无法接受的。QuickFind 给了我们一个重要的启示并查集的设计本质上是find和union操作之间的时间权衡。QuickFind 选择了极端偏向find的一端。2.2 QuickUnion引入“树形结构”优化合并操作QuickUnion 采取了不同的策略。它不再要求同一集合的元素拥有相同的id而是用树形结构来组织集合。parent[i]存储的是元素i的父节点。根节点的父节点指向自己。这样find(x)操作需要沿着父链向上追溯直到找到根节点。union(x, y)操作则只需要将一棵树的根节点连接到另一棵树的根节点上。我们来看源码class QuickUnionUF: def __init__(self, n): # 初始化每个元素的父节点指向自己 self.parent list(range(n)) def find(self, p): # 查找根节点不断向上追溯直到找到父节点是自己的节点根节点 while p ! self.parent[p]: p self.parent[p] return p def connected(self, p, q): return self.find(p) self.find(q) def union(self, p, q): # 合并操作找到p和q的根节点将其中一个根节点的父指针指向另一个根节点 rootP self.find(p) rootQ self.find(q) if rootP rootQ: return # 将rootP的父节点设置为rootQ这样两棵树就合并了 self.parent[rootP] rootQ关键点分析union的优化union操作不再需要遍历数组它只修改一个指针self.parent[rootP] rootQ。时间复杂度取决于find操作。find的代价find操作现在需要沿着树向上爬。在最好的情况下树是平衡的find是 O(log N)。但在最坏的情况下如果union操作总是将大树接到小树下面可能会形成一条长长的“链”退化成一个链表此时find操作会退化到 O(N)。核心问题QuickUnion 的union操作很随意它没有考虑两棵树的大小或高度。盲目的连接是导致树退化的根本原因。虽然它比 QuickFind 在合并密集的场景下可能更好但最坏情况下的性能依然不理想。QuickUnion 让我们看到了希望通过树形结构我们有机会将union的成本降下来。但它也暴露了新的问题如何避免树退化成链这引出了并查集优化的两个经典策略。3. 从 QuickUnion 到工业级实现优化策略深度解析原始的 QuickUnion 只是一个半成品。真正的工业级并查集实现如 Java 的java.util.concurrent.ConcurrentHashMap内部使用的 Disjoint Set或各种算法竞赛模板都会基于它进行两项至关重要的优化按秩合并和路径压缩。3.1 按秩合并避免树的不平衡生长“秩”可以理解为树的高度的一个上界。我们引入一个rank[]数组或size[]数组在union时总是将“秩”较小的树连接到“秩”较大的树的根节点下。class WeightedQuickUnionUF: def __init__(self, n): self.parent list(range(n)) self.size [1] * n # 记录每棵树的大小节点数 def find(self, p): while p ! self.parent[p]: p self.parent[p] return p def union(self, p, q): rootP self.find(p) rootQ self.find(q) if rootP rootQ: return # 按大小秩合并小树接在大树下 if self.size[rootP] self.size[rootQ]: self.parent[rootP] rootQ self.size[rootQ] self.size[rootP] else: self.parent[rootQ] rootP self.size[rootP] self.size[rootQ]为什么这样做有效这保证了合并后的树的高度增长尽可能缓慢。可以证明通过按秩合并任何节点的深度都不会超过log N。因此find操作的时间复杂度被优化到了 O(log N)。这是一个巨大的进步但它还不是终点。3.2 路径压缩在查找时“压平”访问路径路径压缩的想法更巧妙既然find(x)的目的是找到根节点那么在查找的过程中为什么不顺便把沿途经过的所有节点都直接挂到根节点下面呢这样下次再查找这些节点时路径就会大大缩短。有两种常见的路径压缩实现隔代压缩在查找过程中让当前节点指向它的“祖父”节点。def find(self, p): while p ! self.parent[p]: # 将p的父节点指向它的祖父节点 self.parent[p] self.parent[self.parent[p]] p self.parent[p] return p完全压缩使用递归在找到根节点后在回溯的过程中将路径上所有节点的父节点都设置为根节点。def find(self, p): if p ! self.parent[p]: # 递归查找根节点并将当前节点的父节点直接设为根节点 self.parent[p] self.find(self.parent[p]) return self.parent[p]完全压缩的效果更彻底它使得每一次find操作后从该节点到根节点的路径上的所有节点都直接指向根节点。虽然递归调用有额外的开销但在实际应用中其带来的性能收益是决定性的。当“按秩合并”遇上“路径压缩”它们的组合产生了神奇的化学反应。理论分析表明在同时使用这两种优化后find和union操作的摊还时间复杂度是 O(α(n))这是一个比 O(log N) 还要快得多的“近乎常数”的时间复杂度。对于任何实际可能的数据规模比如 N 小于宇宙中的原子数α(n) 都不会超过 5。这意味着在工程实践中你可以认为并查集的操作是常数时间的。4. 实战如何将并查集思维应用到具体问题中理解了原理和优化我们来看看如何用并查集解决实际问题。关键在于将问题模型转化为“动态连通性”问题。例题岛屿数量LeetCode 200给你一个由 1陆地和 0水组成的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。常规解法是 DFS/BFS 遍历网格。但并查集提供了一种不同的视角初始化将每个 1 的格子视为一个独立的集合。动态合并遍历网格对于每个 1 的格子查看其右方和下方的邻居避免重复。如果邻居也是 1则进行union操作将它们所在的集合合并。统计结果遍历所有 1 的格子通过find操作找到其根节点统计不同根节点的数量即为岛屿数量。class Solution: def numIslands(self, grid: List[List[str]]) - int: if not grid: return 0 rows, cols len(grid), len(grid[0]) # 初始化并查集大小为网格中所有格子的数量 uf UnionFind(rows * cols) # 首先统计所有‘1’的位置 count_ones 0 for r in range(rows): for c in range(cols): if grid[r][c] 1: count_ones 1 # 遍历网格进行合并 for r in range(rows): for c in range(cols): if grid[r][c] 1: # 将二维坐标转换为一维索引 idx r * cols c # 只检查右方和下方的邻居避免重复合并 if r 1 rows and grid[r1][c] 1: uf.union(idx, (r1) * cols c) if c 1 cols and grid[r][c1] 1: uf.union(idx, r * cols (c1)) # 统计独立的集合数量 # 注意并查集中包含了所有格子包括‘0’我们需要从中找出根节点是‘1’且不重复的集合 root_set set() for r in range(rows): for c in range(cols): if grid[r][c] 1: root_set.add(uf.find(r * cols c)) return len(root_set) # 更巧妙的做法在union时每成功合并一次就将初始的‘1’的数量减1。 # 最终剩下的数量就是岛屿数。这里为了清晰展示并查集的使用采用了上述方法。从这个例子我们可以提炼出并查集的通用解题框架建模识别问题中的“元素”和“连通关系”。元素通常是节点、格子、变量等连通关系通常是相邻、相等、有边相连等。初始化为每个元素创建独立的集合。动态合并根据题目给出的关系逐步调用union操作。查询与统计在需要时通过find操作查询元素的归属或者统计集合数量、集合大小等信息。其他典型应用场景网络连接检查判断两台计算机是否在同一个网络中。朋友圈/社交网络快速判断两人是否间接认识。最小生成树算法Kruskal 算法的核心就是使用并查集来判断加入一条边是否会形成环。变量名等价性在编译器的寄存器分配或代码优化中判断两个变量名是否等价。图像处理像素连通区域标记。5. 避坑指南与工程实践建议即使理解了算法在真正编码时还是会遇到一些坑。下面是一些关键的实践要点。5.1 初始化与索引处理并查集通常用数组实现元素编号从 0 到 N-1。如果你的问题中元素 ID 不是连续的或者是从 1 开始的你需要建立一个映射关系。# 假设有 M 个元素ID 不连续 elements [1001, 1002, 1005, 2008] id_to_index {elem: idx for idx, elem in enumerate(elements)} # 建立映射 uf UnionFind(len(elements)) # 当需要 union(1001, 1005) 时 uf.union(id_to_index[1001], id_to_index[1005])5.2 “按秩合并”与“路径压缩”的代码模板下面是一个结合了“按大小合并”和“递归路径压缩”的工业级并查集模板建议理解和记忆class UnionFind: def __init__(self, n): self.parent list(range(n)) self.size [1] * n # 记录集合大小 self.count n # 记录当前集合总数可选 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.size[rootX] self.size[rootY]: rootX, rootY rootY, rootX # 交换保证 rootX 是大树根 self.parent[rootY] rootX self.size[rootX] self.size[rootY] self.count - 1 # 集合数减少 return True # 合并成功 def connected(self, x, y): return self.find(x) self.find(y)5.3 性能考量与边界情况递归深度递归实现的路径压缩在极端情况下如 Python 默认递归深度限制可能导致栈溢出。对于超大规模数据N 10^6可以考虑使用迭代版本的find。def find_iterative(self, x): # 先找到根节点 root 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内存与初始化parent和size数组的大小是 O(N)。初始化时间复杂度也是 O(N)。确保你的 N 在内存允许范围内。并查集是离线算法它适合处理动态添加关系、然后查询的场景。如果所有关系边一开始就全部给出有时使用 BFS/DFS 预处理整个图可能更简单。但并查集在需要持续动态合并和查询的场景中无可替代。5.4 如何选择QuickFind vs. (优化后的)QuickUnion这是一个简单的决策流程绝大多数情况无脑选择带按秩合并和路径压缩的 QuickUnion。它是工程实践中的标准答案提供了近乎常数的摊还时间复杂度。仅当极端情况如果你的场景是初始化后几乎只有find操作union操作极少甚至没有例如关系图是静态的你只是要海量查询那么 QuickFind 的 O(1) 查询可能有一丝理论优势。但在实践中这种场景很少且优化后的 QuickUnion 的find也足够快。学习目的理解 QuickFind 和原始 QuickUnion 是理解优化策略的基础。它们清晰地展示了算法设计中的权衡思想。并查集的精妙之处在于它用如此简单的数据结构数组和逻辑找爸爸、认爸爸解决了如此广泛的一类问题。它不像动态规划那样有复杂的递推公式也不像图论算法那样有繁多的变种。它的核心就是find和union以及背后的优化思想。掌握它不仅仅是掌握了一个算法模板更是掌握了一种将复杂动态关系问题抽象为集合合并与查询的思维能力。下次当你遇到需要维护“分组”、“连通块”、“等价类”的问题时不妨先想一想这个问题能用并查集来建模吗 并查集：从QuickFind到QuickUnion，掌握动态连通性问题的数据结构思维
你有没有遇到过这样的场景一个看似简单的“分组”问题却因为数据量巨大、关系动态变化导致用数组、哈希表甚至图论都写得异常复杂性能还上不去比如社交网络里判断两个人是否属于同一个朋友圈或者游戏里判断两个像素点是否连通又或者编译器里判断两个变量名是否指向同一个内存地址。这类问题的核心其实就一句话高效地管理一组动态变化的、具有“归属”关系的元素集合。你需要的不是一个复杂的算法而是一个能直接抓住问题本质的“数据结构思维”。今天要聊的并查集就是为这类问题而生的。很多人第一次接触并查集会觉得它很“玄学”——几个数组操作怎么就解决了这么复杂的问题它的名字Union-Find也透着一种抽象感。这篇文章我们不打算从枯燥的定义开始。我想带你从一次真实的“踩坑”体验出发看看为什么常规思路会失效然后一步步拆解并查集的核心思想最后深入到两种最经典的实现——QuickFind 和 QuickUnion 的源码层面理解它们为何一个“快查”一个“快并”以及如何根据你的场景做出选择。你会发现并查集真正强大的地方不在于它有多高深而在于它用极简的抽象解决了工程中一大类“关系维护”的痛点。1. 从一次“分组”需求崩溃看并查集要解决的核心问题假设你正在处理一个用户关系系统。最初你有 10 个用户编号 0 到 9他们互不相识。随着时间推移用户之间会建立“好友”关系。你的系统需要频繁回答一个问题“用户A和用户B目前是否在同一个社交圈即通过好友关系间接连通”第一反应用数组或列表记录分组。你可能会创建一个数组group[]group[i]表示用户i所属的组号。初始时group [0,1,2,3,4,5,6,7,8,9]每人自成一组。 当用户 1 和用户 2 成为好友你需要合并他们所在的组。于是你遍历整个数组把所有group[i] 2的项都改成group[i] 1或者反过来。一次合并操作时间复杂度是 O(N)。 这还没完。用户 2 又和用户 3 成为好友。现在你需要合并组1包含用户1,2和组3。你又得遍历数组找出所有属于组3的用户把他们归到组1。随着合并越来越多组号会变得混乱合并操作的成本始终是 O(N)。第二反应用邻接表建图然后用 BFS/DFS 判断连通性。这确实能准确判断任意两点是否连通。但是每次查询“用户A和用户B是否连通”你都需要从A点出发做一次图遍历BFS/DFS时间复杂度是 O(NE)在最坏情况下接近 O(N^2)。对于需要每秒处理成千上万次查询的系统这是不可接受的。这时并查集的价值就凸显出来了。它专门为这种场景设计动态连通性关系边是逐步添加的不是一开始就给定的静态图。高效查询需要极快地回答“两个元素是否属于同一集合”。高效合并需要将两个集合合并成一个。并查集的核心 API 只有两个find(x): 查找元素x属于哪个集合通常返回集合的“代表元”。union(x, y): 将元素x和y所在的集合合并。它的目标就是让这两个操作的平均时间复杂度接近常数级 O(α(n))其中 α(n) 是增长极慢的反阿克曼函数对于任何实际应用中的 n其值不会超过 5。并查集真正解决的不是“如何表示关系”而是“如何用最小的维护成本支撑海量的动态关系查询”。2. 理解并查集的“森林”隐喻与两种核心操作并查集最巧妙的抽象是将集合表示为“树”或“森林”。每个集合是一棵树树根就是该集合的“代表元”。判断两个元素是否属于同一集合就等价于判断它们的树根是否相同。初始时每个元素都是一棵独立的树只有根节点。我们用数组parent[]来表示这个森林。parent[i]存储元素i的父节点。如果i是根节点一种常见的做法是令parent[i] i自环或者parent[i] -1。基于这个“森林”模型我们来看两种最基础的实现策略它们分别代表了在find查和union并之间的不同权衡。2.1 QuickFind为了“查得快”牺牲“并”的效率QuickFind 的思路非常直接让同一个集合里的所有元素都直接指向同一个“代表元”根节点。这样find(x)操作只需要一次数组访问parent[x]时间复杂度是严格的 O(1)。我们来看看它的源码实现逻辑。假设有 N 个元素0 到 N-1class QuickFindUF: def __init__(self, n): # 初始化每个元素的id即集合代表元就是自己 self.id list(range(n)) def find(self, p): # 查找直接返回元素p的集合id return self.id[p] def connected(self, p, q): # 判断连通性比较两个元素的集合id是否相同 return self.find(p) self.find(q) def union(self, p, q): # 合并操作这是QuickFind的关键也是其瓶颈所在 pid self.find(p) qid self.find(q) if pid qid: return # 已经在同一集合无需操作 # 将属于pid集合的所有元素全部改为属于qid集合 for i in range(len(self.id)): if self.id[i] pid: self.id[i] qid关键点分析find为什么快因为它只是self.id[p]一次数组访问。这就是“QuickFind”名字的由来。union为什么慢因为它需要遍历整个数组for i in range(len(self.id))将所有属于pid集合的元素id[i]修改为qid。一次union操作的时间复杂度是 O(N)。适用场景如果你的应用特点是find查询操作极其频繁而union合并操作非常少那么 QuickFind 可能是合适的。但在绝大多数动态连通性问题中合并操作和查询操作是交错发生的O(N) 的合并成本是无法接受的。QuickFind 给了我们一个重要的启示并查集的设计本质上是find和union操作之间的时间权衡。QuickFind 选择了极端偏向find的一端。2.2 QuickUnion引入“树形结构”优化合并操作QuickUnion 采取了不同的策略。它不再要求同一集合的元素拥有相同的id而是用树形结构来组织集合。parent[i]存储的是元素i的父节点。根节点的父节点指向自己。这样find(x)操作需要沿着父链向上追溯直到找到根节点。union(x, y)操作则只需要将一棵树的根节点连接到另一棵树的根节点上。我们来看源码class QuickUnionUF: def __init__(self, n): # 初始化每个元素的父节点指向自己 self.parent list(range(n)) def find(self, p): # 查找根节点不断向上追溯直到找到父节点是自己的节点根节点 while p ! self.parent[p]: p self.parent[p] return p def connected(self, p, q): return self.find(p) self.find(q) def union(self, p, q): # 合并操作找到p和q的根节点将其中一个根节点的父指针指向另一个根节点 rootP self.find(p) rootQ self.find(q) if rootP rootQ: return # 将rootP的父节点设置为rootQ这样两棵树就合并了 self.parent[rootP] rootQ关键点分析union的优化union操作不再需要遍历数组它只修改一个指针self.parent[rootP] rootQ。时间复杂度取决于find操作。find的代价find操作现在需要沿着树向上爬。在最好的情况下树是平衡的find是 O(log N)。但在最坏的情况下如果union操作总是将大树接到小树下面可能会形成一条长长的“链”退化成一个链表此时find操作会退化到 O(N)。核心问题QuickUnion 的union操作很随意它没有考虑两棵树的大小或高度。盲目的连接是导致树退化的根本原因。虽然它比 QuickFind 在合并密集的场景下可能更好但最坏情况下的性能依然不理想。QuickUnion 让我们看到了希望通过树形结构我们有机会将union的成本降下来。但它也暴露了新的问题如何避免树退化成链这引出了并查集优化的两个经典策略。3. 从 QuickUnion 到工业级实现优化策略深度解析原始的 QuickUnion 只是一个半成品。真正的工业级并查集实现如 Java 的java.util.concurrent.ConcurrentHashMap内部使用的 Disjoint Set或各种算法竞赛模板都会基于它进行两项至关重要的优化按秩合并和路径压缩。3.1 按秩合并避免树的不平衡生长“秩”可以理解为树的高度的一个上界。我们引入一个rank[]数组或size[]数组在union时总是将“秩”较小的树连接到“秩”较大的树的根节点下。class WeightedQuickUnionUF: def __init__(self, n): self.parent list(range(n)) self.size [1] * n # 记录每棵树的大小节点数 def find(self, p): while p ! self.parent[p]: p self.parent[p] return p def union(self, p, q): rootP self.find(p) rootQ self.find(q) if rootP rootQ: return # 按大小秩合并小树接在大树下 if self.size[rootP] self.size[rootQ]: self.parent[rootP] rootQ self.size[rootQ] self.size[rootP] else: self.parent[rootQ] rootP self.size[rootP] self.size[rootQ]为什么这样做有效这保证了合并后的树的高度增长尽可能缓慢。可以证明通过按秩合并任何节点的深度都不会超过log N。因此find操作的时间复杂度被优化到了 O(log N)。这是一个巨大的进步但它还不是终点。3.2 路径压缩在查找时“压平”访问路径路径压缩的想法更巧妙既然find(x)的目的是找到根节点那么在查找的过程中为什么不顺便把沿途经过的所有节点都直接挂到根节点下面呢这样下次再查找这些节点时路径就会大大缩短。有两种常见的路径压缩实现隔代压缩在查找过程中让当前节点指向它的“祖父”节点。def find(self, p): while p ! self.parent[p]: # 将p的父节点指向它的祖父节点 self.parent[p] self.parent[self.parent[p]] p self.parent[p] return p完全压缩使用递归在找到根节点后在回溯的过程中将路径上所有节点的父节点都设置为根节点。def find(self, p): if p ! self.parent[p]: # 递归查找根节点并将当前节点的父节点直接设为根节点 self.parent[p] self.find(self.parent[p]) return self.parent[p]完全压缩的效果更彻底它使得每一次find操作后从该节点到根节点的路径上的所有节点都直接指向根节点。虽然递归调用有额外的开销但在实际应用中其带来的性能收益是决定性的。当“按秩合并”遇上“路径压缩”它们的组合产生了神奇的化学反应。理论分析表明在同时使用这两种优化后find和union操作的摊还时间复杂度是 O(α(n))这是一个比 O(log N) 还要快得多的“近乎常数”的时间复杂度。对于任何实际可能的数据规模比如 N 小于宇宙中的原子数α(n) 都不会超过 5。这意味着在工程实践中你可以认为并查集的操作是常数时间的。4. 实战如何将并查集思维应用到具体问题中理解了原理和优化我们来看看如何用并查集解决实际问题。关键在于将问题模型转化为“动态连通性”问题。例题岛屿数量LeetCode 200给你一个由 1陆地和 0水组成的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。常规解法是 DFS/BFS 遍历网格。但并查集提供了一种不同的视角初始化将每个 1 的格子视为一个独立的集合。动态合并遍历网格对于每个 1 的格子查看其右方和下方的邻居避免重复。如果邻居也是 1则进行union操作将它们所在的集合合并。统计结果遍历所有 1 的格子通过find操作找到其根节点统计不同根节点的数量即为岛屿数量。class Solution: def numIslands(self, grid: List[List[str]]) - int: if not grid: return 0 rows, cols len(grid), len(grid[0]) # 初始化并查集大小为网格中所有格子的数量 uf UnionFind(rows * cols) # 首先统计所有‘1’的位置 count_ones 0 for r in range(rows): for c in range(cols): if grid[r][c] 1: count_ones 1 # 遍历网格进行合并 for r in range(rows): for c in range(cols): if grid[r][c] 1: # 将二维坐标转换为一维索引 idx r * cols c # 只检查右方和下方的邻居避免重复合并 if r 1 rows and grid[r1][c] 1: uf.union(idx, (r1) * cols c) if c 1 cols and grid[r][c1] 1: uf.union(idx, r * cols (c1)) # 统计独立的集合数量 # 注意并查集中包含了所有格子包括‘0’我们需要从中找出根节点是‘1’且不重复的集合 root_set set() for r in range(rows): for c in range(cols): if grid[r][c] 1: root_set.add(uf.find(r * cols c)) return len(root_set) # 更巧妙的做法在union时每成功合并一次就将初始的‘1’的数量减1。 # 最终剩下的数量就是岛屿数。这里为了清晰展示并查集的使用采用了上述方法。从这个例子我们可以提炼出并查集的通用解题框架建模识别问题中的“元素”和“连通关系”。元素通常是节点、格子、变量等连通关系通常是相邻、相等、有边相连等。初始化为每个元素创建独立的集合。动态合并根据题目给出的关系逐步调用union操作。查询与统计在需要时通过find操作查询元素的归属或者统计集合数量、集合大小等信息。其他典型应用场景网络连接检查判断两台计算机是否在同一个网络中。朋友圈/社交网络快速判断两人是否间接认识。最小生成树算法Kruskal 算法的核心就是使用并查集来判断加入一条边是否会形成环。变量名等价性在编译器的寄存器分配或代码优化中判断两个变量名是否等价。图像处理像素连通区域标记。5. 避坑指南与工程实践建议即使理解了算法在真正编码时还是会遇到一些坑。下面是一些关键的实践要点。5.1 初始化与索引处理并查集通常用数组实现元素编号从 0 到 N-1。如果你的问题中元素 ID 不是连续的或者是从 1 开始的你需要建立一个映射关系。# 假设有 M 个元素ID 不连续 elements [1001, 1002, 1005, 2008] id_to_index {elem: idx for idx, elem in enumerate(elements)} # 建立映射 uf UnionFind(len(elements)) # 当需要 union(1001, 1005) 时 uf.union(id_to_index[1001], id_to_index[1005])5.2 “按秩合并”与“路径压缩”的代码模板下面是一个结合了“按大小合并”和“递归路径压缩”的工业级并查集模板建议理解和记忆class UnionFind: def __init__(self, n): self.parent list(range(n)) self.size [1] * n # 记录集合大小 self.count n # 记录当前集合总数可选 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.size[rootX] self.size[rootY]: rootX, rootY rootY, rootX # 交换保证 rootX 是大树根 self.parent[rootY] rootX self.size[rootX] self.size[rootY] self.count - 1 # 集合数减少 return True # 合并成功 def connected(self, x, y): return self.find(x) self.find(y)5.3 性能考量与边界情况递归深度递归实现的路径压缩在极端情况下如 Python 默认递归深度限制可能导致栈溢出。对于超大规模数据N 10^6可以考虑使用迭代版本的find。def find_iterative(self, x): # 先找到根节点 root 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内存与初始化parent和size数组的大小是 O(N)。初始化时间复杂度也是 O(N)。确保你的 N 在内存允许范围内。并查集是离线算法它适合处理动态添加关系、然后查询的场景。如果所有关系边一开始就全部给出有时使用 BFS/DFS 预处理整个图可能更简单。但并查集在需要持续动态合并和查询的场景中无可替代。5.4 如何选择QuickFind vs. (优化后的)QuickUnion这是一个简单的决策流程绝大多数情况无脑选择带按秩合并和路径压缩的 QuickUnion。它是工程实践中的标准答案提供了近乎常数的摊还时间复杂度。仅当极端情况如果你的场景是初始化后几乎只有find操作union操作极少甚至没有例如关系图是静态的你只是要海量查询那么 QuickFind 的 O(1) 查询可能有一丝理论优势。但在实践中这种场景很少且优化后的 QuickUnion 的find也足够快。学习目的理解 QuickFind 和原始 QuickUnion 是理解优化策略的基础。它们清晰地展示了算法设计中的权衡思想。并查集的精妙之处在于它用如此简单的数据结构数组和逻辑找爸爸、认爸爸解决了如此广泛的一类问题。它不像动态规划那样有复杂的递推公式也不像图论算法那样有繁多的变种。它的核心就是find和union以及背后的优化思想。掌握它不仅仅是掌握了一个算法模板更是掌握了一种将复杂动态关系问题抽象为集合合并与查询的思维能力。下次当你遇到需要维护“分组”、“连通块”、“等价类”的问题时不妨先想一想这个问题能用并查集来建模吗