并查集：从原理到实战，掌握高效处理动态连通性的数据结构

1. 项目概述：并查集，一种被低估的高效数据结构

如果你写过一些需要处理分组、连通性或者动态合并集合的代码，大概率会和我一样，经历过用数组、链表甚至哈希表来维护这些关系，结果代码越写越复杂，性能还上不去的窘境。直到我遇到了并查集（Union-Find Set），才真正体会到什么叫“大道至简”。这玩意儿名字听起来有点学术，但它的核心思想简单到令人发指，效率却高得惊人，在解决某些特定类型的问题时，几乎是降维打击。

简单来说，并查集就是一种用来管理元素分组情况的数据结构。它主要支持两种操作：查找（Find）某个元素属于哪个集合，以及合并（Union）两个元素所在的集合。听起来是不是平平无奇？但它的魔力在于，通过一些巧妙的优化，这两种操作的平均时间复杂度可以接近常数级别 O(α(n))，这里的 α(n) 是阿克曼函数的反函数，增长极其缓慢，对于任何在宇宙可观测范围内的 n，这个值都不会超过 5。这意味着，无论你要处理十亿还是百亿的数据量，并查集的操作都快得飞起。

它最适合解决什么样的问题呢？我举几个我实际踩过坑的例子你就明白了。比如社交网络里的好友关系推荐（判断两个人是否在同一个朋友圈子）、游戏开发中的像素连通区域标记、编译器中的变量等价类分析，甚至是最近很火的那些分布式系统中的集群节点状态管理，底层逻辑都绕不开并查集。以前我用深度优先搜索（DFS）去做连通性判断，数据量一大就超时，换成并查集后，代码从几十行精简到十几行，速度提升了好几个数量级。所以，无论你是正在备战算法面试的学生，还是需要处理海量关联数据的工程师，花点时间吃透并查集，绝对是一笔稳赚不赔的投资。

2. 核心原理与设计思想拆解

2.1 “树”的直觉：如何用父指针表示集合

并查集最精妙的设计，在于它用“树”这种结构来代表一个集合。我们不再显式地存储一个集合里有哪些元素，而是为每个元素维护一个指向其“父亲”的指针。同一个集合里的所有元素，最终都会指向同一个根节点（Root）。这个根节点，就是这个集合的“代表元”。

初始状态下，每个元素自成一家，它的父亲就是它自己。当我们说“查找元素x属于哪个集合”时，其实就是沿着它的父亲指针一路向上找，直到找到那个父亲是自己的根节点。这个根节点的编号，就唯一标识了x所在的集合。

那么“合并两个集合”呢？操作更简单：找到两个元素各自的根节点，然后把其中一个根节点的父亲，指向另一个根节点。这样一来，两棵树就变成了一棵树，两个集合也就合并成了一个。

我刚开始学的时候，总觉得这太“简陋”了，能行吗？后来才明白，这种“只存关系，不存全集”的方式，正是它节省空间和时间的核心。我们只关心“谁和谁是一伙的”，而不需要知道这个团伙里具体有谁、是怎么排座的。这种抽象，恰好匹配了连通性问题的本质。

2.2 关键操作剖析：Find与Union的朴素实现

我们先来看看最直接、不加任何优化的实现，这能帮助我们理解基础逻辑，也更能体会后面优化的重要性。

查找（Find）操作：就是一个简单的递归或循环，不断向上寻找父亲，直到根节点。

def find_naive(x, parent): while parent[x] != x: # 如果x不是根节点 x = parent[x] # 向上移动一层 return x

这个方法很直观，但有个明显问题：如果这棵树变得很高（比如一条长链），那么每次查找都需要遍历整条链，时间复杂度会退化到 O(n)。

合并（Union）操作：先找到两个元素的根，然后连接它们。

def union_naive(x, y, parent): rootX = find_naive(x, parent) rootY = find_naive(y, parent) if rootX != rootY: # 如果不在同一个集合 parent[rootX] = rootY # 将rootX的父亲设为rootY

这个朴素合并策略的问题是随意的：总是把第一个集合的根接到第二个集合的根上。如果碰巧总是把大树接到小树上，很容易就会造出一棵深度很大的树，从而拖慢后续所有查找操作的速度。

注意：在并查集的语境里，“合并”永远是指合并集合，而不是合并两个单独的元素。代码中的union(x, y)，其含义是“如果x和y不在同一个集合，则将它们所在的集合合并”。这个语义一定要清晰，否则在理解复杂问题时容易混淆。

2.3 路径压缩：让查找“一步登天”的魔法

朴素查找慢，是因为树可能很高。那么，一个很自然的想法是：在查找某个节点的根时，能不能顺便把沿途所有节点的父亲都直接改成根节点呢？这就是路径压缩。

def find_with_path_compression(x, parent): if parent[x] != x: # 递归找到根节点，并在回溯时将当前节点的父指针直接指向根 parent[x] = find_with_path_compression(parent[x], parent) return parent[x]

非递归的迭代写法也更清晰：

def find_with_path_compression_iter(x, parent): root = x # 第一次循环：找到根节点root while parent[root] != root: root = parent[root] # 第二次循环：将路径上所有节点的父亲直接指向根 while parent[x] != root: next_node = parent[x] parent[x] = root x = next_node return root

路径压缩的效果是革命性的。经过一次查找后，从该节点到根节点的整条路径都被“压平”了。下次再查找这个节点或其路径上的任何节点，都只需要一步。虽然单次操作的成本略高（因为要修改指针），但摊还下来，后续的查询效率得到了巨大提升。实测中，这是提升并查集性能最关键的一步，我几乎会在所有场景下默认开启它。

2.4 按秩合并：维持树的平衡之道

路径压缩主要优化了“查”，而“并”的策略也会影响树的结构。如果我们能在合并时，有意识地将小树挂到大树下，就能避免树变得过高。这里的“大小”可以指树的节点数量（按大小合并），也可以指树的高度（按秩合并）。通常使用“秩”这个术语，它是一个近似高度的上界。

我们需要一个额外的数组rank来记录每个根节点的秩。

def union_by_rank(x, y, parent, rank): rootX = find(x, parent) # 假设find已包含路径压缩 rootY = find(y, parent) if rootX != rootY: # 按秩合并：将秩小的树接到秩大的树下 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))。

实操心得：在绝大多数情况下，我推荐同时使用路径压缩和按秩合并。这被称为并查集的“完全优化”版本。虽然代码多了几行，但带来的性能收益是决定性的。除非是在一些对内存极度敏感或者合并操作有特殊顺序要求的极端场景，否则无脑用这个组合就对了。

3. 代码实现与关键细节

3.1 基础模板：一个完全优化的并查集类

理解了原理，我们来看一个可以直接“抄作业”的Python实现模板。这个模板集成了路径压缩和按秩合并，是应对算法竞赛和工程问题的通用利器。

class UnionFind: def __init__(self, n): """ 初始化并查集。 :param n: 元素个数，元素编号通常为 0 到 n-1 """ self.parent = list(range(n)) # 初始时，每个元素的父亲是自己 self.rank = [0] * n # 初始秩为0 self.count = n # 当前集合的个数（可选，便于统计） def find(self, x): """ 查找元素x的根节点，附带路径压缩。 """ # 路径压缩（迭代版） while self.parent[x] != x: # 这里采用“隔代压缩”，虽然不是完全压缩，但效率更高，代码更简洁 self.parent[x] = self.parent[self.parent[x]] x = self.parent[x] return x # 路径压缩（递归版，更直观但可能有递归深度限制） # if self.parent[x] != x: # self.parent[x] = self.find(self.parent[x]) # return self.parent[x] def union(self, x, y): """ 合并元素x和y所在的集合。 """ rootX = self.find(x) rootY = self.find(y) if rootX == rootY: return # 已经在同一集合，无需合并 # 按秩合并 if self.rank[rootX] < self.rank[rootY]: self.parent[rootX] = rootY elif self.rank[rootX] > self.rank[rootY]: self.parent[rootY] = rootX else: # 秩相等，任意合并，这里选择将rootY接到rootX下 self.parent[rootY] = rootX self.rank[rootX] += 1 self.count -= 1 # 集合数减少一个 def connected(self, x, y): """ 判断元素x和y是否属于同一个集合。 """ return self.find(x) == self.find(y) def get_count(self): """ 返回当前集合的个数。 """ return self.count

关键细节解析：

1. 初始化：parent数组的索引代表元素编号，值代表其父节点。初始化时parent[i] = i是标准做法。
2. find中的隔代压缩：代码中self.parent[x] = self.parent[self.parent[x]]这一行是迭代实现路径压缩的技巧。它让节点在向上寻找根的过程中，每次跳两级（指向父亲的父亲），虽然不是一次性压到根，但多次操作后效果等同于完全压缩，且避免了递归开销，性能更好。
3. union中的按秩合并：比较rank是关键。只当两个根节点秩相等时，才需要增加新根的秩。这个“秩”并不是精确的高度，而是一个上界，在路径压缩后可能会降低，但这不影响合并策略的正确性。
4. count的维护：这个变量不是必须的，但在很多问题中非常有用，比如判断最后有多少个连通分量。在初始化时等于总元素数n，每次成功合并后减1。

3.2 变体与扩展：应对复杂场景

基础的并查集模板能解决80%的问题，但有些场景需要稍作变通。

场景一：需要知道集合大小有时我们不仅要知道元素是否连通，还想知道所在集合有多少个成员。可以额外维护一个size数组。

class UnionFindWithSize: def __init__(self, n): self.parent = list(range(n)) self.size = [1] * n # 每个集合的初始大小为1 def find(self, x): # ... 路径压缩同上 ... def union(self, x, y): rootX = self.find(x) rootY = self.find(y) if rootX == rootY: return # 按集合大小合并：将小集合挂到大集合下 if self.size[rootX] < self.size[rootY]: self.parent[rootX] = rootY self.size[rootY] += self.size[rootX] else: self.parent[rootY] = rootX self.size[rootX] += self.size[rootY]

这里用size替代了rank作为合并的依据，同样能保证树高平衡。size数组在回溯到根节点后才是有效的。

场景二：元素不是连续整数如果元素是字符串、对象或者不连续的数字，我们可以用字典（哈希表）来代替数组。

class UnionFindDict: 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 # 路径压缩 while self.parent[x] != x: self.parent[x] = self.parent[self.parent[x]] x = self.parent[x] return x def union(self, x, y): rootX = self.find(x) rootY = self.find(y) if rootX != rootY: # 按秩合并逻辑与数组版相同 if self.rank[rootX] < self.rank[rootY]: self.parent[rootX] = rootY elif self.rank[rootX] > self.rank[rootY]: self.parent[rootY] = rootX else: self.parent[rootY] = rootX self.rank[rootX] += 1

这种实现更灵活，但哈希表的开销会比数组稍大。

注意事项：在算法题中，如果元素编号明确是从0或1开始的连续整数，务必使用数组版本。数组通过索引直接访问，其常数时间开销远小于哈希表，在性能敏感的场合差异显著。我曾在一次线上比赛中，因为偷懒用了字典版，导致一个大数据集用例超时，换成数组后立刻通过，教训深刻。

4. 典型应用场景与实战解析

并查集的价值，必须在具体问题中才能充分体现。下面我结合几个经典和高频的场景，拆解如何将问题“翻译”成并查集操作。

4.1 场景一：动态连通性问题（LeetCode 经典题）

这是并查集的“本行”。题目通常直接给出一些连接关系，然后询问两个点是否连通，或者最终有多少个连通分量。

例题：LeetCode 547. 省份数量题目描述：有 n 个城市，其中一些彼此相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。省份是一组直接或间接相连的城市。给你一个 n x n 的矩阵 isConnected，其中isConnected[i][j] = 1表示第 i 个城市和第 j 个城市直接相连，为 0 表示不直接相连。返回矩阵中省份的数量。

解题思路：

1. 初始化一个大小为 n 的并查集。
2. 遍历矩阵的上三角（或下三角，避免重复），如果isConnected[i][j] == 1，就执行union(i, j)。
3. 遍历结束后，统计并查集中根节点仍然是自己的元素个数，即为省份数量。也可以直接返回我们模板中维护的count。

def findCircleNum(isConnected): n = len(isConnected) uf = UnionFind(n) for i in range(n): for j in range(i+1, n): # 遍历上三角 if isConnected[i][j] == 1: uf.union(i, j) return uf.get_count()

心得：这类问题的关键，在于准确地将“相连”这个条件映射为一次union操作。矩阵是对称的，所以只需遍历一半即可。最终集合的个数就是连通分量的个数。

4.2 场景二：处理“敌对”或“分组”关系（扩展域并查集）

有些问题不仅有关联，还有排斥关系。例如“已知A和B是朋友，B和C是敌人，A和D是敌人，问C和D是什么关系？”这类问题，可以用扩展域（也叫种类并查集）的思想来解决。

核心思想：将每个元素拆分成多个逻辑节点，分别代表它在不同“种类”或“关系”下的身份。通常，如果元素有 k 种互斥关系，就拆成 k 份。

例题：LeetCode 990. 等式方程的可满足性题目描述：给定一个由字符串数组表示的方程式，每个方程式equations[i]长度为 4，格式为a==b或a!=b。判断所有方程式是否可能同时成立。

解题思路：

1. 等式具有传递性，这天然适合用并查集。
2. 难点在于不等式a!=b。它要求 a 和 b不能在同一个集合里。
3. 我们可以先处理所有等式==，将它们连通。
4. 再检查所有不等式!=，如果不等式两边的字符已经在同一个集合里，就产生了矛盾，返回False。

def equationsPossible(equations): # 因为变量是小写字母，最多26个 uf = UnionFind(26) base = ord('a') # 第一遍：处理所有等式，建立连通关系 for eq in equations: if eq[1] == '=': x = ord(eq[0]) - base y = ord(eq[3]) - base uf.union(x, y) # 第二遍：检查所有不等式，是否与已建立的连通关系矛盾 for eq in equations: if eq[1] == '!': x = ord(eq[0]) - base y = ord(eq[3]) - base if uf.connected(x, y): return False return True

心得：对于这种带不等关系的问题，“先处理等式，再验证不等式”是一个通用且有效的策略。并查集在这里完美地维护了等式的传递性。

更复杂的“敌人的朋友是敌人”这类问题，则需要用到扩展域，将每个元素 i 拆成两个域：i表示“朋友域”，i+n表示“敌人域”。当说 i 和 j 是朋友时，合并(i, j)以及(i+n, j+n)；当说 i 和 j 是敌人时，合并(i, j+n)以及(i+n, j)。通过检查矛盾（例如 i 既和 j 是朋友又是敌人）来判断是否满足条件。这种思路在解决“二分图判断”、“食物链”等问题时非常强大。

4.3 场景三：网格类问题中的连通块计数与合并

在图像处理、岛屿问题等网格场景中，并查集提供了一种不同于DFS/BFS的、增量式的连通块维护方法。

例题：LeetCode 200. 岛屿数量（并查集解法）题目描述：给你一个由'1'（陆地）和'0'（水）组成的二维网格，计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

DFS/BFS是更直观的解法，但并查集解法有其独特优势，尤其是在需要动态添加陆地（离线查询）的场景下。思路：将每个陆地格子看作一个元素。遍历网格，当遇到一个陆地时，先将其视为一个独立的岛屿（集合）。然后查看其上方和左方的格子（因为我们是按行遍历，只需看这两个方向即可），如果也是陆地，就进行union操作。最终，集合的数量就是岛屿的数量。

def numIslands(grid): if not grid: return 0 rows, cols = len(grid), len(grid[0]) uf = UnionFind(rows * cols) # 将二维坐标映射到一维 count_water = 0 for i in range(rows): for j in range(cols): if grid[i][j] == '1': # 当前是陆地 idx = i * cols + j # 检查上方 if i > 0 and grid[i-1][j] == '1': uf.union(idx, (i-1)*cols + j) # 检查左方 if j > 0 and grid[i][j-1] == '1': uf.union(idx, i*cols + (j-1)) else: count_water += 1 # 岛屿数量 = 总集合数 - 水的格子数（每个水格子自成一个集合） return uf.get_count() - count_water

心得：在网格问题中使用并查集，核心是二维坐标到一维索引的映射(i, j) -> i * cols + j。另一个技巧是，由于并查集初始化时认为所有格子都是独立集合，最后需要减去水格子的数量。这种方法的优势在于，如果题目变成“动态添加陆地，并实时查询岛屿数”，并查集可以高效处理，而DFS/BFS则需要每次都重新遍历。

5. 性能分析、常见陷阱与调试技巧

5.1 时间复杂度：为什么是O(α(n))？

这是并查集最令人称道的一点。单次的find或union操作，在最坏情况下（未经优化）是 O(n)。但经过路径压缩和按秩合并的优化后，其摊还时间复杂度是 O(α(n))。

摊还分析考虑的是连续执行 m 次操作的总时间，然后除以 m 得到平均每次的时间。α(n) 是阿克曼函数的反函数，其增长速度慢到难以想象。可以近似认为，在人类所有可能遇到的数据规模下，α(n) 不超过 5。因此，在实践中，我们常说并查集的操作是“近乎常数时间”的。

重要提示：这个优秀的复杂度是建立在“摊还”基础上的。如果你在算法题中需要对每个元素进行单次查找，那么并查集并不比直接扫描数组快。它的威力体现在需要大量、反复、交错执行find和union操作的场景。例如，在Kruskal最小生成树算法中，需要对所有边按权重排序后，依次尝试合并边的两端点，这个过程中并查集的操作次数与边数成正比，此时其高效性才无可替代。

5.2 空间复杂度

并查集通常需要两个数组：parent和rank（或size）。每个数组的大小都是元素个数 n。因此，空间复杂度是 O(n)。对于字典实现的变体，空间复杂度也是 O(n)，但常数因子更大一些。

5.3 常见“坑点”与避坑指南

在我使用并查集的过程中，踩过不少坑，这里总结几个最常见的：

1. 初始化错误：最经典的错误是忘记初始化parent[i] = i和rank[i] = 0。特别是parent数组，如果初始化为 -1 或其他值，find函数会陷入死循环或得到错误结果。务必在构造函数中显式初始化。

2. 在union中错误使用find：

   # 错误写法！ def union_bad(x, y): if self.parent[x] != self.parent[y]: # 比较的不是根节点！ self.parent[x] = y

   必须通过find找到根节点再进行合并。直接比较parent[x]和parent[y]是无效的，因为它们可能只是中间节点。

3. 路径压缩的副作用：路径压缩会改变树的结构，使得树高信息（rank）不再精确。但正如前文所述，rank在按秩合并中只是一个上界估计，即使被高估了，合并逻辑依然是正确的，不会影响复杂度。但如果你需要依赖精确的树高做其他计算，就需要小心了。

4. 统计集合大小时的错误：当你维护一个size数组时，size的值只在根节点上有意义。在find操作进行路径压缩后，非根节点的size值就过时了。因此，永远通过size[find(x)]来获取元素x所在集合的大小。

5. 元素编号从1开始：很多题目输入的元素编号是从1开始的。如果你习惯性地创建大小为 n 的数组，访问parent[n]就会越界。安全的做法是创建大小为n+1的数组，并忽略索引0。或者，在读取输入时，将所有编号减1，转换为0-based索引。我强烈推荐后者，可以避免很多边界错误。

5.4 调试技巧：可视化与状态打印

当并查集行为不符合预期时，最有效的调试方法就是打印其内部状态。我通常会写一个辅助方法：

def debug_print(uf): n = len(uf.parent) print("索引:", list(range(n))) print("父节点:", uf.parent) print("秩:", uf.rank) # 打印每个元素的根 roots = [uf.find(i) for i in range(n)] print("根节点:", roots) # 按集合分组打印 from collections import defaultdict groups = defaultdict(list) for i in range(n): groups[roots[i]].append(i) print("集合分组:", dict(groups))

在关键操作（如几次union之后）调用这个函数，可以清晰地看到数据结构的变化，快速定位是合并逻辑错误还是查找逻辑错误。

另一个技巧是画图。对于小规模数据，在纸上手动模拟并查集的操作流程，画出parent指针的变化，是理解其工作原理和排查错误的最佳方式。