一、什么是并查集
并查集（Union-Find），也称为不相交集合（Disjoint Set Union，DSU），是一种用于处理集合合并与查询问题的树形数据结构。它主要支持两种操作：
- Find（查找）： 确定某个元素属于哪个集合，通常返回该集合的"代表元素"（根节点）
- Union（合并）： 将两个不相交的集合合并为一个集合
并查集的核心思想是：用树（森林）来表示集合，每个集合用一棵树表示，树的根节点作为该集合的唯一标识。初始状态下，每个元素各自独立构成一棵只有根节点的树。
核心能力
- 判断两个元素是否属于同一个集合（is_connected）
- 快速合并两个集合（union）
- 查询当前连通分量数量（count）
- 在近似 O(1) 的时间复杂度内完成以上操作（经过路径压缩和按秩合并优化后）
并查集是图论算法中"基础设施"级别的数据结构，广泛应用于连通分量检测、最小生成树、社交网络分析、动态连通性等场景。掌握并查集是算法学习中最具性价比的投资之一。
二、基本数据结构与实现
2.1 核心数据结构
并查集使用一个父指针数组 parent[] 来维护集合关系。parent[i] 表示元素 i 的父节点。当 parent[i] == i 时，i 就是所在集合的根节点。
class UnionFind {
private:
int[] parent;
int[] rank;
int count;
public:
UnionFind(int n) {
count = n;
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
};
初始状态示意图
假设有 6 个元素（0-5），初始化后每个元素都是一棵独立的树：
0 1 2 3 4 5
↑ ↑ ↑ ↑ ↑ ↑
自身 自身 自身 自身 自身 自身
此时连通分量数量 count = 6。
2.2 基础版 Find 操作
查找元素 x 所属集合的根节点。通过沿父指针链向上追溯，直到找到 parent[x] == x 的元素。
int find(int x) {
while (parent[x] != x) {
x = parent[x];
}
return x;
}
2.3 基础版 Union 操作
将两个元素所在的集合合并。先找到各自的根节点，然后将一个根节点指向另一个。
void unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) {
return;
}
parent[rootX] = rootY;
count--;
}
2.4 判断连通性
bool isConnected(int x, int y) {
return find(x) == find(y);
}
int getCount() {
return count;
}
基础版本的问题
基础版本的 Find 和 Union 在最坏情况下时间复杂度为 O(n)。例如，当不断将长链的末端合并到新节点时，树会退化成一条链，Find 操作需要逐层遍历整条链。这在大规模数据下是不可接受的，因此需要引入优化策略。
三、优化策略
3.1 路径压缩（Path Compression）
路径压缩是并查集最重要的优化之一。其核心思想是：在执行 Find 操作时，将路径上所有经过的节点直接连接到根节点上，从而扁平化树结构，加速后续的查找操作。
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
int find(int x) {
int root = x;
while (parent[root] != root) {
root = parent[root];
}
while (x != root) {
int next = parent[x];
parent[x] = root;
x = next;
}
return root;
}
路径压缩的效果
经过路径压缩后，树的深度大大降低。多次 Find 操作后，树几乎被压平为深度接近 2 的扁平结构。每个节点要么是根，要么直接指向根。
注意：路径压缩不改变 rank 值。rank 只反映节点在未压缩时树的高度上界，这一特性保证了按秩合并在路径压缩存在时仍能正常工作。
3.2 按秩合并（Union by Rank）
按秩合并的核心思想是：在合并两个集合时，总是将秩（树的高度）较小的树连接到秩较大的树之下，避免树的不必要增长。
void unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return;
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
count--;
}
按大小合并（Union by Size）
除了按秩合并，另一种常见策略是按大小合并——总是将元素较少的集合合并到元素较多的集合。两种策略效果相近，均能保证树的高度为 O(log n)。
if (size[rootX] < size[rootY]) {
parent[rootX] = rootY;
size[rootY] += size[rootX];
} else {
parent[rootY] = rootX;
size[rootX] += size[rootY];
}
3.3 时间复杂度分析
| 实现方式 |
Union |
Find |
备注 |
| 基础实现（无优化） |
O(n) |
O(n) |
树可能退化成链表 |
| 只按秩合并 |
O(log n) |
O(log n) |
树高保证 ≤ log₂n |
| 只路径压缩 |
O(log n) |
摊销 O(log n) |
扁平化树结构 |
| 路径压缩 + 按秩合并 |
O(α(n)) |
O(α(n)) |
近似 O(1)，反阿克曼函数 |
反阿克曼函数 α(n)
当同时使用路径压缩和按秩合并时，并查集操作的时间复杂度为 O(α(n))，其中 α(n) 是反阿克曼函数（Inverse Ackermann Function）。
α(n) 的增长速度极其缓慢：
- α(10^3) ≈ 3
- α(10^6) ≈ 4
- α(10^100) ≈ 5
- α(2^65536) ≈ 5
对于任何物理世界中可达到的 n，α(n) ≤ 5，因此我们可以认为并查集的操作时间为 近似常数 O(1)。这一结论的严格证明由 Hopcroft 和 Ullman 给出。
四、实现变体与对比
4.1 QuickFind 实现
QuickFind 是并查集最朴素的实现方式。其核心思想是：使用数组存储每个元素所属的集合 ID，同一个集合中的所有元素具有相同的 ID。
class QuickFind {
private:
int[] id;
int count;
public:
QuickFind(int n) {
count = n;
id = new int[n];
for (int i = 0; i < n; i++) id[i] = i;
}
int find(int x) {
return id[x];
}
void unionSets(int x, int y) {
int idX = find(x);
int idY = find(y);
if (idX == idY) return;
for (int i = 0; i < id.length; i++) {
if (id[i] == idX) {
id[i] = idY;
}
}
count--;
}
};
QuickFind 特点：Find 操作是 O(1)，但 Union 操作需要 O(n) 时间遍历整个数组。适用于查询多、合并少的场景。
4.2 QuickUnion 实现
QuickUnion 采用树形结构的父指针表示法，与标准并查集相同。它优化了 Union 的速度，但 Find 可能变慢。
class QuickUnion {
private:
int[] parent;
public:
QuickUnion(int n) {
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int x) {
while (parent[x] != x) x = parent[x];
return x;
}
void unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootX] = rootY;
count--;
}
}
};
4.3 WeightedQuickUnion（带权重优化）
WeightedQuickUnion 是 QuickUnion 的改进版，它通过跟踪树的大小来保证较小的树总是连接到较大的树上，从而避免树的退化。
| 实现方式 |
Find 时间复杂度 |
Union 时间复杂度 |
构造函数 |
| QuickFind |
O(1) |
O(n) |
O(n) |
| QuickUnion |
O(树高) ≈ O(n) |
O(树高) ≈ O(n) |
O(n) |
| WeightedQuickUnion |
O(log n) |
O(log n) |
O(n) |
| WeightedQuickUnion + Path Compression |
O(α(n)) |
O(α(n)) |
O(n) |
五、完整实现（最优版本）
下面给出并查集的最优实现——同时包含路径压缩和按秩合并的完整 C++/Java 风格实现：
class UnionFind {
private:
int[] parent;
int[] rank;
int count;
public:
UnionFind(int n) {
count = n;
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return;
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
count--;
}
boolean isConnected(int x, int y) {
return find(x) == find(y);
}
int getCount() {
return count;
}
};
六、并查集的典型应用
6.1 连通分量检测（Connected Components）
在无向图中，使用并查集可以快速计算出图的连通分量数量。遍历所有边，对每条边的两个端点执行 Union 操作即可。
int countComponents(int n, int[][] edges) {
UnionFind uf = new UnionFind(n);
for (int[] edge : edges) {
uf.unionSets(edge[0], edge[1]);
}
return uf.getCount();
}
6.2 Kruskal 最小生成树算法
Kruskal 算法是并查集最经典的应用之一。其算法步骤如下：
- 将图中所有边按权重从小到大排序
- 初始化并查集，每个顶点自成一个集合
- 从小到大遍历每条边 (u, v, w)：
- 如果 u 和 v 不在同一集合中（即不构成环），将边加入 MST，合并 u 和 v
- 当选中 n-1 条边时停止，得到最小生成树
int kruskal(int n, int[][] edges) {
Arrays.sort(edges, (a, b) -> a[2] - b[2]);
UnionFind uf = new UnionFind(n);
int mstWeight = 0;
int edgeCount = 0;
for (int[] edge : edges) {
if (!uf.isConnected(edge[0], edge[1])) {
uf.unionSets(edge[0], edge[1]);
mstWeight += edge[2];
edgeCount++;
if (edgeCount == n - 1) break;
}
}
return mstWeight;
}
Kruskal vs Prim 算法
- Kruskal：适合稀疏图，时间复杂度 O(E log E)，依赖并查集检测环
- Prim：适合稠密图，时间复杂度 O(V²) 或 O(E log V)，类似 Dijkstra
- 两者都能求出最小生成树，选择取决于图的稠密程度
6.3 好友关系网络（社交网络）
在社交网络中，使用并查集可以快速判断两个用户是否为间接好友（共同好友的好友），或者统计朋友圈数量。
class Solution {
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
UnionFind uf = new UnionFind(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (isConnected[i][j] == 1) {
uf.unionSets(i, j);
}
}
}
return uf.getCount();
}
}
6.4 岛屿数量（并查集解法）
虽然 DFS/BFS 是岛屿问题的标准解法，但并查集同样能优雅地解决这一问题：
int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int rows = grid.length, cols = grid[0].length;
UnionFind uf = new UnionFind(rows * cols);
int[] dirs = {0, 1, 0, -1, 0};
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == '1') {
for (int d = 0; d < 4; d++) {
int nr = r + dirs[d], nc = c + dirs[d + 1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == '1') {
uf.unionSets(r * cols + c, nr * cols + nc);
}
}
}
}
}
Set<Integer> roots = new HashSet<>();
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == '1') {
roots.add(uf.find(r * cols + c));
}
}
}
return roots.size();
}
6.5 等式方程的可满足性
LeetCode 990. 等式方程的可满足性
给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程长度为 4：
形式为 "a==b" 或 "a!=b"。判断是否可以为所有变量分配整数以同时满足所有方程。
解法思路：先处理所有 "==" 等式，将相等变量 Union 到同一集合；再处理所有 "!=" 不等式，如果不等号两端的变量已属于同一集合，则返回 false。
public boolean equationsPossible(String[] equations) {
UnionFind uf = new UnionFind(26);
for (String eq : equations) {
if (eq.charAt(1) == '=') {
uf.unionSets(eq.charAt(0) - 'a', eq.charAt(3) - 'a');
}
}
for (String eq : equations) {
if (eq.charAt(1) == '!') {
if (uf.isConnected(eq.charAt(0) - 'a', eq.charAt(3) - 'a')) {
return false;
}
}
}
return true;
}
七、带权并查集
带权并查集（Weighted Union-Find）
在标准的并查集中，我们只关心元素之间的连通关系（是否在同一集合）。而在一些场景中，我们还需要知道元素之间的相对关系，例如：
- 节点 A 比节点 B 多多少分
- 节点 A 到 B 的距离是多少
- A 和 B 的种类关系（如食物链问题）
带权并查集通过在父指针上附加权重信息来维护这些相对关系。
class WeightedUnionFind {
private:
int[] parent;
double[] weight;
int count;
public:
WeightedUnionFind(int n) {
parent = new int[n];
weight = new double[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
weight[i] = 1.0;
}
}
int find(int x) {
if (parent[x] != x) {
int originalParent = parent[x];
parent[x] = find(parent[x]);
weight[x] *= weight[originalParent];
}
return parent[x];
}
void unionSets(int x, int y, double value) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return;
parent[rootX] = rootY;
weight[rootX] = value * weight[y] / weight[x];
}
double getRatio(int x, int y) {
if (find(x) != find(y)) {
return -1;
}
return weight[x] / weight[y];
}
};
带权并查集的经典题目
- LeetCode 399. 除法求值： 给出 a/b=2.0, b/c=3.0，求 a/c 的值
- LeetCode 721. 账户合并： 合并同名账户下的所有邮箱
- POJ 1182 食物链： 三类动物之间的捕食关系（模 3 余数关系）
7.1 例题：除法求值
public double[] calcEquation(
List<List<String>> equations,
double[] values,
List<List<String>> queries
) {
Map<String, Integer> map = new HashMap<>();
int id = 0;
for (List<String> eq : equations) {
if (!map.containsKey(eq.get(0))) map.put(eq.get(0), id++);
if (!map.containsKey(eq.get(1))) map.put(eq.get(1), id++);
}
WeightedUnionFind uf = new WeightedUnionFind(id);
for (int i = 0; i < equations.size(); i++) {
int a = map.get(equations.get(i).get(0));
int b = map.get(equations.get(i).get(1));
uf.unionSets(a, b, values[i]);
}
double[] result = new double[queries.size()];
for (int i = 0; i < queries.size(); i++) {
String x = queries.get(i).get(0);
String y = queries.get(i).get(1);
if (!map.containsKey(x) || !map.containsKey(y)) {
result[i] = -1.0;
} else {
result[i] = uf.getRatio(map.get(x), map.get(y));
}
}
return result;
}
八、更多应用与扩展
8.1 并查集在图像处理中的应用
在图像处理中，并查集可用于连通区域标记（Connected Component Labeling）。将每个像素视为一个节点，相邻且颜色相近的像素执行 Union 操作，最终得到所有连通区域。
8.2 动态连通性（Dynamic Connectivity）
在网络连接场景中，当网络中的节点可以动态加入或删除连接时，并查集可以高效地回答"节点 A 和 B 是否连通"的查询。典型应用包括：
- 计算机网络： 判断两个路由器是否在同一子网
- 电路设计： 检测 PCB 板上两点是否连通
- 社交网络： 判断两个用户是否在同一社交圈
8.3 并查集的可持久化
通过可持久化线段树（主席树）实现并查集的可持久化版本，可以回退到历史版本。这在一些需要撤销操作的场景中非常有用（如离线动态图连通性问题）。
8.4 并查集的撤销操作
标准的并查集不支持撤销（即 Union 操作不可逆）。但通过按秩合并 + 栈记录操作历史，可以实现可撤销并查集：
class RollbackUnionFind {
int[] parent;
int[] size;
Stack<int[]> history;
RollbackUnionFind(int n) {
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
history = new Stack<>();
}
int find(int x) {
while (parent[x] != x) x = parent[x];
return x;
}
boolean unionSets(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) {
history.push(new int[]{-1, -1, -1, -1});
return false;
}
if (size[ra] < size[rb]) {
int t = ra; ra = rb; rb = t;
}
history.push(new int[]{ra, size[ra], rb, parent[rb]});
parent[rb] = ra;
size[ra] += size[rb];
return true;
}
void rollback() {
int[] prev = history.pop();
if (prev[0] != -1) {
int ra = prev[0], sa = prev[1];
int rb = prev[2], prb = prev[3];
size[ra] = sa;
parent[rb] = prb;
}
}
}
九、LeetCode 经典习题
以下题目可以帮助巩固并查集的学习：
| 题目编号 |
题目名称 |
难度 |
考察知识点 |
| 200 |
岛屿数量 |
中等 |
二维坐标映射、连通分量 |
| 547 |
省份数量（朋友圈） |
中等 |
邻接矩阵、连通分量计数 |
| 684 |
冗余连接 |
中等 |
Union-Find 检测环 |
| 721 |
账户合并 |
中等 |
字符串映射、集合合并 |
| 990 |
等式方程的可满足性 |
中等 |
先等后不等、冲突检测 |
| 399 |
除法求值 |
中等 |
带权并查集、图论 |
| 128 |
最长连续序列 |
困难 |
Union-Find 或哈希表 |
| 765 |
情侣牵手 |
困难 |
贪心 + Union-Find |
| 778 |
水位上升的泳池中游泳 |
困难 |
二分 + Union-Find |
十、核心要点总结
- 定义： 并查集是处理不相交集合合并与查询的树形数据结构，核心操作包括 Find（查找根）和 Union（合并集合）
- 路径压缩： 在 Find 操作中将沿途所有节点直接指向根，大大降低树的高度。时间复杂度从不优化的 O(n) 降低到近似 O(1)
- 按秩合并： 在 Union 操作中将秩较小的树合并到秩较大的树，保证树高不超过 log₂n。与路径压缩配合使用效果最优
- 时间复杂度： 同时使用路径压缩和按秩合并后，单次操作的时间复杂度为 O(α(n))，α 是反阿克曼函数，可视为常数
- 三种变体： QuickFind（Find O(1) Union O(n)）、QuickUnion（Find 可能 O(n)）、WeightedQuickUnion（Find/Union O(log n)）
- 经典应用： 连通分量检测、Kruskal 最小生成树、社交网络朋友圈、等式约束判定、图像连通区域标记
- 带权并查集： 在父指针上附加权重，用于维护集合内元素之间的相对关系（比例、差值、种类等）
- 可撤销并查集： 通过按大小合并（避免路径压缩）+ 栈记录操作历史实现"后悔"机制
- 适用场景特征： 需要维护动态连通性、集合合并操作频繁、查询操作量大、不需要从集合中删除元素
十一、进一步思考
深入探讨
- 为什么路径压缩和按秩合并同时使用时光复杂度能达到 O(α(n))？ 这涉及复杂的摊还分析（Amortized Analysis）。核心思路是：每次路径压缩都会"展平"树结构，使得后续操作的成本更低。通过将节点按秩分组并进行势能分析，可以证明总的操作次数为 O(m α(n))。
- 并查集在处理动态图（Dynamic Graph）中的应用： 当图的边可以动态增加时（没有删除），并查集可以在线性时间内处理所有连通性查询。但当边可以删除时，需要使用动态树（Link-Cut Tree）或离线分治（Offline Divide & Conquer）来解决。
- 并查集与图染色问题的联系： 利用带权并查集可以解决二分图判定问题。通过维护节点到根节点的"奇偶性"关系（模 2 权值），可以在 Union 操作时检测是否产生奇环。
- 并查集在并行计算中的潜力： 由于并查集操作之间存在数据依赖，完全并行化比较困难。但近年来的研究提出了可并行化的并查集算法（如 Wait-Free Union-Find），在 GPU 等并行架构上实现了高效连通分量计算。
工程实践建议
- 始终同时使用路径压缩和按秩合并，以获取近似 O(1) 的优异性能
- 使用数组而非指针实现 parent 数组，以获得更好的缓存局部性和更低的访存开销
- 在 C++ 中注意递归深度：递归实现 Find 更简洁，但在极端情况下可能导致栈溢出；建议使用迭代实现
- 在 Java 中优先使用 int 数组而非 ArrayList，避免装箱拆箱开销
- 按大小合并通常比按秩合并更适用于可撤销场景，因为 size 信息在路径压缩时不需要维护
- 千万级节点的并查集运行依然高效，内存占用仅约 8-16 MB（视优化策略而定）