并查集算法精讲：原理、优化与实战应用

1. 项目概述：为什么并查集是解决连通性问题的“瑞士军刀”

如果你写过一些算法题，或者处理过网络节点、社交关系、图像分割这类问题，大概率会碰到一个经典场景：给你一堆元素，你需要快速判断任意两个元素是否属于同一个集合，或者需要将两个元素所在的集合合并。最直观的想法可能是用数组或者哈希表来记录每个元素的“老大”，但当你需要频繁进行“找老大”和“合并帮派”这两个操作时，朴素的实现很容易就超时了。这时候，并查集（Union-Find）就该登场了。

并查集，也叫不相交集合（Disjoint-Set），是一种专门为处理这类动态连通性问题而设计的数据结构。它的核心操作只有两个：find（查找某个元素所属集合的代表元，也就是“找老大”）和union（合并两个元素所在的集合，也就是“帮派合并”）。别看它结构简单，在路径压缩和按秩合并这两种优化技巧的加持下，这两个操作的平均时间复杂度可以接近常数级别，效率高得惊人。我最初接触它是在解决一个“朋友圈”问题，当时用深度优先搜索（DFS）去遍历，数据量一大就卡住了，换成并查集后，代码简洁了，速度也提升了好几个数量级，那种感觉就像发现了一把趁手的“神器”。

它解决的问题非常普遍：社交网络中的好友关系（判断两个人是否间接认识）、计算机网络中的主机连通性、编译器中的变量等价性分析、游戏开发中的像素区域标记（图像分割）、最小生成树算法（Kruskal算法）等等。可以说，只要是涉及“分组”和“连通”的场景，并查集都是你应该首先考虑的工具之一。这篇文章，我就结合自己刷题和项目中的实际使用经验，带你彻底搞懂并查集的原理、实现、优化以及那些容易踩的坑。

2. 核心原理与数据结构设计：从数组到森林的抽象

理解并查集，关键在于理解它的两种等价视角：数组视角和森林视角。数组视角更贴近底层实现，便于编码；森林视角则更直观，有助于理解操作逻辑。

2.1 森林视角：帮派与树形结构

我们可以把每个独立的集合想象成一个“帮派”，每个帮派有一个“掌门人”（代表元）。所有成员都以树形结构组织起来，最终都指向掌门人。

初始时，有 N 个独立的元素，我们就创建 N 棵只有一个节点的树，每个节点都是自己所在树的根（即自己是自己的掌门人）。 当需要合并两个元素a和b所在的集合时，我们找到a的根节点rootA和b的根节点rootB。如果它们不同，说明属于不同帮派，那么就把其中一个根节点挂到另一个根节点下面，让其中一个帮派归顺另一个。至于谁归顺谁，后面“按秩合并”优化会详细说。 查找操作find(x)，就是从节点x开始，沿着父指针一路向上找，直到找到根节点。这个根节点就是元素x所在集合的唯一标识。

这个模型非常直观，union就是让两棵树合并成一棵，find就是寻根问祖。

2.2 数组视角：底层实现的核心

在代码中，我们通常用一个长度固定的数组parent来实现这片森林。数组的索引代表元素（假设元素编号从 0 到 N-1），数组的值代表这个元素的父节点。

初始化时，每个元素的父节点都是它自己：parent[i] = i。这对应着森林中 N 棵单节点树。find(x)操作：写一个循环或递归函数，不断查询parent[x]，直到parent[x] == x，这个x就是根。union(a, b)操作：先调用find(a)得到rootA，调用find(b)得到rootB。如果rootA != rootB，则执行parent[rootA] = rootB或parent[rootB] = rootA，将一棵树的根指向另一棵树的根。

注意：这里有一个初学者极易混淆的点。union操作合并的是两个集合的根，而不是直接合并a和b这两个节点。错误的写法parent[a] = b只是把a个人挂到了b手下，如果a原本手下有小弟，那么这些小弟就和a断开了联系，导致集合分裂。所以，必须先find到根，再合并根，这是并查集操作不可违背的铁律。

2.3 复杂度分析与优化动机

在最坏情况下，如果我们总是将新节点挂到一棵长链的末尾，那么这棵树就会退化成一条链表。此时find操作的时间复杂度会退化到 O(N)。对于需要执行数十万甚至上百万次操作的场景，这是不可接受的。

因此，我们必须对朴素的并查集进行优化，目标就是让树尽可能保持扁平。两大核心优化技术——路径压缩和按秩合并——应运而生。它们能双管齐下，将单次操作的均摊时间复杂度降低到惊人的 O(α(N))，其中 α(N) 是增长极其缓慢的反阿克曼函数，对于任何在宇宙可观测范围内的实际数据量，α(N) 都不会超过 5，因此可以认为是常数时间。

3. 核心优化技术详解：路径压缩与按秩合并

理解了基础操作，我们来深入拆解让并查集效率产生质变的两大优化。这是并查集最精华的部分，也是面试和实际应用中必考必用的内容。

3.1 路径压缩：让树变扁平的“捷径”

路径压缩的核心思想非常巧妙：既然find(x)的目的是找到根，那么在查找的过程中，我们能不能“顺便”把沿途所有节点的父节点都直接指向根呢？这样，下次再查找这些节点时，就能一步到位。

实现方式（递归版）：

def find(x): if parent[x] != x: # 如果不是根节点 parent[x] = find(parent[x]) # 递归查找根，并沿途将父节点设为根 return parent[x] # 返回根节点

这个递归实现非常简洁。它不仅在查找根，还在返回的过程中，将x到根路径上的所有节点的parent都直接指向了最终的根节点。

实现方式（迭代版）： 有些语言递归深度可能受限，或者为了极致性能，可以用迭代实现。

def find(x): root = x while parent[root] != root: # 先找到根节点 root root = parent[root] # 路径压缩：将从 x 到 root 路径上的所有节点直接指向 root while parent[x] != root: next_node = parent[x] parent[x] = root x = next_node return root

迭代版先找到根，再重新走一遍路径进行压缩。虽然代码稍长，但逻辑清晰。

实操心得：在大部分情况下，递归版的路径压缩就足够了，代码也更易读。但在一些极端递归深度可能很大的场景（虽然并查集优化后树很扁平，深度不大），或者追求极限性能时，可以考虑迭代版。我个人的习惯是，在算法竞赛中用递归版求快，在生产环境的底层库中可能会用迭代版以求稳。

3.2 按秩合并：避免退化成链的“智慧”

路径压缩主要优化了“查”，而按秩合并则优化了“并”。它的目的是在合并两棵树时，总是将“矮”的树接到“高”的树下面，从而避免树的高度快速增长，为后续的路径压缩创造更好的条件。

“秩”可以理解为树高的一个上界估计。我们引入一个额外的数组rank（或size）。 初始化时，每个元素独立成树，秩为0或1（根据定义，可以是高度0，也可以是大小1，两种定义都可行，但合并逻辑稍有不同）。

按高度合并（更常见）：

• rank[i]初始为 0。
• 合并时，比较两棵树的根rootA和rootB的rank。
  • 如果rank[rootA] < rank[rootB]，则将rootA挂到rootB下。rootB的高度不变。
  • 如果rank[rootA] > rank[rootB]，则将rootB挂到rootA下。
  • 如果两者相等，则任意选择一方挂到另一方下，但作为新根的树的rank需要加 1（因为两棵树高度相同，合并后整体高度增加了1）。

按大小合并：

• size[i]初始为 1，代表集合的元素个数。
• 合并时，总是将元素个数少的集合的根，挂到元素个数多的集合的根下。并更新新根的size。

两种方式都能有效控制树高。按高度合并更直接地控制了高度这个指标；按大小合并则可能在某些特定问题（如需要知道集合大小）时更方便。在时间复杂度分析上，两者都能达到同样的优化效果。

带按秩合并的union操作示例（按高度）：

def union(a, b): rootA = find(a) rootB = find(b) if rootA == rootB: return # 已经在同一集合，无需合并 if rank[rootA] < rank[rootB]: parent[rootA] = rootB elif rank[rootA] > rank[rootB]: parent[rootB] = rootA else: # 高度相等，任意合并，但新根高度+1 parent[rootA] = rootB rank[rootB] += 1

3.3 优化组合的效果与实现选择

路径压缩和按秩合并可以同时使用，它们并不冲突。同时使用时，rank数组记录的高度信息可能不再是准确的树高（因为路径压缩会改变树的结构，降低高度），但它仍然是一个有效的“秩”的估计，能很好地指导合并顺序。

在实际编码中，一个标准且高效的并查集模板通常包含以下部分：

1. parent数组。
2. rank或size数组（用于按秩合并）。
3. 带路径压缩的find函数。
4. 带按秩合并判断的union函数。

对于是否必须使用按秩合并，我的经验是：在算法竞赛或对性能要求极高的场景，务必同时使用两者。如果只是解决一个简单问题，数据量不大，可以只使用路径压缩，代码更短。但养成好习惯，写出完整的优化模板，能避免很多潜在的性能陷阱。

4. 完整实现与代码模板

理论讲完了，我们来点实在的。下面给出几个不同语言版本的、同时包含路径压缩和按秩合并的并查集完整模板。你可以直接复制使用，并理解每一行的作用。

4.1 Python 实现模板

Python版本以其简洁性著称，非常适合算法原型设计和面试。

class UnionFind: def __init__(self, n): # 初始化，每个元素的父节点是自己，秩为0 self.parent = list(range(n)) self.rank = [0] * 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.rank[rootX] < self.rank[rootY]: self.parent[rootX] = rootY elif self.rank[rootX] > self.rank[rootY]: self.parent[rootY] = rootX else: # 秩相等，任意合并，新根秩+1 self.parent[rootX] = rootY self.rank[rootY] += 1 return True # 合并成功 def connected(self, x, y): # 判断两个元素是否连通 return self.find(x) == self.find(y)

模板使用解析：

• __init__: 构造函数，传入元素个数n。这里同时初始化了parent和rank。
• find: 使用了递归形式的路径压缩，一行核心代码self.parent[x] = self.find(self.parent[x])同时完成了查找和压缩。
• union: 先找到两个元素的根，如果根不同则按秩合并。函数返回一个布尔值，表示是否执行了合并操作，这在某些场景（如Kruskal算法中判断是否添加了边）很有用。
• connected: 一个非常常用的辅助函数，封装了两次find和比较操作。

4.2 Java 实现模板

Java版本更注重严谨和性能，适合工程应用。

public class UnionFind { private int[] parent; private int[] rank; // private int count; // 可选：连通分量计数 public UnionFind(int n) { parent = new int[n]; rank = new int[n]; // count = n; for (int i = 0; i < n; i++) { parent[i] = i; rank[i] = 0; // 初始高度为0 } } // 带路径压缩的查找 public int find(int x) { // 迭代版路径压缩 while (parent[x] != x) { parent[x] = parent[parent[x]]; // 路径压缩的优化：隔代压缩 x = parent[x]; } return x; // 递归版同样可用： // if (parent[x] != x) { // parent[x] = find(parent[x]); // } // return parent[x]; } // 按秩合并 public boolean union(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX == rootY) { return false; } if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else { parent[rootX] = rootY; rank[rootY] += 1; } // count--; // 合并后连通分量减少 return true; } public boolean connected(int x, int y) { return find(x) == find(y); } // public int getCount() { return count; } }

Java模板要点：

• 在find方法中，我给出了迭代版的一个小技巧：parent[x] = parent[parent[x]]。这被称为“隔代压缩”，它虽然没有递归版压缩得那么彻底（一次性压到根），但在循环中实现简单，且效果也很好，能显著降低树高。
• 注释中保留了递归版的写法，以及连通分量计数count的示例。在Kruskal算法中，count可以用来判断是否已形成最小生成树。

4.3 C++ 实现模板

C++模板追求极致的运行效率。

class UnionFind { public: vector<int> parent, rank; UnionFind(int n) : parent(n), rank(n, 0) { iota(parent.begin(), parent.end(), 0); // 用0,1,2,...填充parent } int find(int x) { // 路径压缩（递归版） if (parent[x] != x) { parent[x] = find(parent[x]); } return parent[x]; // 迭代版路径压缩： // while (parent[x] != x) { // parent[x] = parent[parent[x]]; // x = parent[x]; // } // return x; } bool unite(int x, int y) { // 合并，有些实现叫union，但union是C++关键字 int rootX = find(x); int rootY = find(y); if (rootX == rootY) return false; if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else { parent[rootY] = rootX; rank[rootX] += 1; } return true; } bool connected(int x, int y) { return find(x) == find(y); } };

C++模板注意：

• 使用vector存储parent和rank。
• 初始化时使用了iota函数来快速填充parent数组为 0, 1, 2, ...。
• 合并函数命名为unite，因为union是C/C++的关键字。
• 同样提供了递归和迭代两种find实现。

重要提示：无论哪种语言，核心逻辑都是一致的。选择哪个模板取决于你的使用场景。在在线编程平台刷题时，我建议你准备好自己最熟悉的那个模板，在解题时快速默写出来，能节省大量时间。

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

懂了原理和模板，我们来看看并查集到底能解决哪些实际问题。我会通过几个经典问题，带你一步步分析如何将问题建模成并查集，并写出解决方案。

5.1 场景一：朋友圈问题（LeetCode 547）

问题描述：有n个朋友，给出一个n x n的矩阵M表示朋友关系。M[i][j] = 1表示第i个人和第j个人是直接朋友。朋友关系具有传递性：如果 A 是 B 的朋友，B 是 C 的朋友，那么 A 和 C 也是间接朋友。求总共有多少个朋友圈（连通分量）。

建模与解决：

1. 初始化：创建并查集，大小为n。初始时，每个人自成一个朋友圈。
2. 合并操作：遍历矩阵M的上三角（或下三角，因为矩阵是对称的）。当M[i][j] == 1时，说明i和j是直接朋友，调用union(i, j)将他们所在的朋友圈合并。
3. 统计结果：遍历所有人0到n-1，对每个人调用find(i)找到其朋友圈的根。根的不同种类数，就是朋友圈的数量。更高效的做法是，在并查集内部维护一个count变量，初始为n，每次成功执行union后count--，最终count就是答案。

代码要点：

def findCircleNum(M): n = len(M) uf = UnionFind(n) for i in range(n): for j in range(i+1, n): # 只遍历一半，避免重复 if M[i][j] == 1: uf.union(i, j) # 统计不同的根 roots = set() for i in range(n): roots.add(uf.find(i)) return len(roots)

这个问题完美体现了并查集处理“传递性连通关系”的优势。如果用DFS/BFS，你需要为每个未访问的人做一次遍历，而并查集在构建关系的过程中就自然完成了分组。

5.2 场景二：岛屿数量 II（LeetCode 305 - 离线版思想）

这是一个动态问题：一开始全是水（0），然后陆续在某个位置添加陆地（1），每次添加后都需要实时返回当前岛屿的数量。并查集非常适合处理这种动态连通性问题。

建模与解决：

1. 初始化一个m*n大小的并查集，以及一个二维数组grid记录当前陆地状态，初始全为0（水）。岛屿数量count初始为0。
2. 当在位置(r, c)添加一块陆地时： a. 如果该位置已经是陆地，直接返回当前count。 b. 否则，将其标记为陆地，count++（先假设它是一个新岛屿）。 c. 查看其上下左右四个相邻位置。如果某个邻居是陆地，则说明这块新陆地可能与旧岛屿相连。调用union合并新陆地与邻居陆地所在的集合。如果合并成功，意味着两个独立的岛屿连接成了一个，count--。
3. 每次操作后，count就是当前的岛屿数。

代码逻辑片段：

def numIslands2(m, n, positions): uf = UnionFind(m * n) grid = [[0]*n for _ in range(m)] count = 0 res = [] dirs = [(0,1), (1,0), (0,-1), (-1,0)] for r, c in positions: if grid[r][c] == 1: # 已是陆地 res.append(count) continue idx = r * n + c # 二维坐标转一维索引 grid[r][c] = 1 count += 1 for dr, dc in dirs: nr, nc = r + dr, c + dc if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1: nidx = nr * n + nc if uf.union(idx, nidx): # 合并成功 count -= 1 res.append(count) return res

这个例子展示了并查集如何优雅地维护动态集合的连通分量个数，其效率远高于每次添加陆地后都进行一次全图的DFS/BFS搜索。

5.3 场景三：等式方程的可满足性（LeetCode 990）

问题描述：给定一个字符串数组equations，每个元素是"a==b"或"a!=b"的形式。判断所有这些等式和不等式是否能够同时成立。

建模与解决：

1. 由于变量是小写字母，最多26个，我们可以初始化一个大小为26的并查集。
2. 处理所有等式：遍历equations，对于每个等式"a==b"，将变量a和b进行合并（union(a_index, b_index)）。等式建立了变量的连通关系。
3. 检查所有不等式：再次遍历equations，对于每个不等式"a!=b"，检查变量a和b的根是否相同（find(a_index) == find(b_index)）。如果相同，说明根据前面的等式推导，a和b必须相等，这与不等式矛盾，返回false。
4. 如果所有不等式检查都通过，返回true。

核心思想：并查集在这里维护了变量的等价类。所有通过等式相连的变量属于同一个等价类（连通分量）。不等式则要求两个变量必须属于不同的等价类。这个“先处理连接关系，再验证约束条件”的模式，在解决这类约束满足问题时非常常见。

5.4 场景四：Kruskal 最小生成树算法

这是图论中并查集的经典应用。Kruskal算法用于在加权无向图中找出一棵最小生成树。

算法步骤：

1. 将图中所有边按权重从小到大排序。
2. 初始化一个并查集，每个顶点自成一个集合。
3. 按权重从小到大遍历每条边(u, v, w)： a. 检查顶点u和v是否已经连通（find(u) == find(v)）。 b. 如果不连通，则这条边可以加入最小生成树（不会形成环），调用union(u, v)合并两个顶点所在的集合，并将边权累加。 c. 如果已连通，则跳过（加入这条边会形成环）。
4. 当加入的边数达到顶点数 - 1时，算法结束。

并查集在其中的作用就是高效地判断两个顶点是否已在同一连通分量中，从而避免环的产生。如果没有并查集，判断连通性需要DFS/BFS，会使算法复杂度变差。

实战经验：在这些应用场景中，最关键的一步是问题建模——识别出问题本质是动态的连通性判断或集合合并。一旦确认，套用并查集模板往往能迎刃而解。多练习这类问题，能快速提升你的“并查集嗅觉”。

6. 常见问题、调试技巧与性能陷阱

即使理解了原理，在实际编码中还是会遇到各种问题。下面是我在大量使用并查集后总结的一些常见坑点和调试心得。

6.1 初始化错误

问题：忘记初始化parent数组为parent[i]=i，或者忘记初始化rank数组。现象：find函数可能陷入死循环（如果parent[i]是默认值0），或者按秩合并逻辑出错。检查：构造函数第一件事就是完成数组的初始化。这是最基础的步骤，务必检查。

6.2 合并了非根节点

问题：在union函数中，直接parent[a] = b。现象：导致集合结构破坏。例如，原有结构a->rootA,b->rootB，错误合并后变成a->b，a脱离了原来的集合rootA，而rootA下的其他节点再也找不到a了。纠正：必须union(find(a), find(b))，即合并两个集合的根。

6.3 路径压缩的副作用

问题：路径压缩后，树的高度发生变化，此时rank数组记录的高度信息不再准确。现象：这本身不是问题，因为按秩合并中的rank在优化后应被理解为“秩”（一个上界），而非精确高度。即使不准确，它依然能很好地指导合并。不要在路径压缩后去更新rank值，这是不必要的，也会增加复杂度。

6.4 复杂度理解误区

问题：认为每次find或union都是 O(α(N))。澄清：O(α(N)) 是均摊时间复杂度。单次操作在最坏情况下可能达不到这个效率，但经过一系列操作后，平均每次的成本极低。在算法分析时，我们可以放心地将其视为常数时间。

6.5 如何调试并查集

当程序出现逻辑错误，怀疑是并查集问题时，可以采取以下方法：

1. 打印状态：在关键操作（union后）打印parent数组。观察合并是否正确发生，根节点是否正确更新。
2. 小数据测试：构造一个极小的、能复现问题的测试用例，手动模拟并查集的操作过程，与程序输出对比。
3. 可视化：对于复杂问题，可以尝试在纸上画出元素和操作步骤，模拟并查集的变化，这是理解其行为最有效的方式。
4. 检查find函数：确保你的find函数确实实现了路径压缩。可以在调用前后打印相关节点的父节点，看是否被正确压缩到根。

6.6 空间与时间权衡

• 空间：并查集需要 O(N) 的额外空间存储parent和rank数组。对于元素数量巨大的场景（例如数千万以上），这可能成为瓶颈。此时可以考虑使用哈希表来实现动态的并查集（元素ID不一定是连续的整数），但常数时间会稍大。
• 时间：虽然均摊复杂度极优，但初始化仍需 O(N) 时间。如果问题中元素总数 N 很大，但实际参与合并操作的元素很少，可以考虑使用懒初始化的并查集（用字典存储parent和rank，只在元素第一次出现时初始化），以节省初始化的开销。

7. 扩展与变种：应对更复杂的需求

标准的并查集处理“是否连通”的问题。但实际问题可能更复杂，需要对其进行扩展。

7.1 带权并查集

有时我们不仅需要知道元素是否连通，还需要知道它们之间的某种“关系”或“距离”。例如，在“除法求值”问题中，我们需要处理a / b = value这样的关系，并查询任意两个变量的商。

核心思想：在parent数组之外，再维护一个weight数组。weight[x]表示节点x到其父节点parent[x]的“权值”（比如比值、距离差等）。

• find操作：在递归查找根的过程中，需要同时更新权值。路径压缩时，节点x的新权值是其到根节点的累积权值。
• union操作：已知a到其根ra的权值为w_a，b到其根rb的权值为w_b，现在要合并ra和rb，并根据给定的a和b之间的关系val，推导出ra到rb的权值w，然后执行parent[ra] = rb并设置weight[ra] = w。

带权并查集是并查集学习中的一个难点，但理解后能解决一大类更复杂的关联性问题。关键在于推导出合并时权值的计算公式，并在路径压缩时正确维护权值。

7.2 可撤销并查集

在有些问题中，我们需要支持“回退”操作，即撤销最近的一次union。标准并查集由于路径压缩破坏了历史结构，无法直接撤销。

实现方式：不使用路径压缩，只使用按秩合并（按大小合并更好）。将每次union操作影响的节点（通常是较小的那棵树的根）和其原来的父节点信息记录下来。撤销时，只需要根据记录的信息恢复parent和size数组即可。这种并查集常用于需要离线处理、分治或回溯的场景。

7.3 动态并查集

标准并查集大小固定。动态并查集允许在运行时添加新的元素。实现很简单，内部使用哈希表（字典）代替数组来存储parent和rank。当访问一个不存在的元素时，将其初始化为一个新的集合（父节点为自己，秩为0）。

class DynamicUnionFind: def __init__(self): self.parent = {} self.rank = {} def find(self, 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): # ... 合并逻辑与标准版类似，注意处理不存在的元素

掌握了这些基础、优化、应用和扩展知识，你已经具备了在实战中灵活运用并查集解决各类连通性问题的能力。记住，并查集不仅仅是一个数据结构，更是一种解决问题的思想——将动态的、复杂的连通关系，用简单的合并与查找来维护。下次当你遇到需要分组、归类、判断连通性的问题时，不妨先想想：能不能用并查集？