🧮 并查集 (Union Find / Disjoint Set Union)
难度 / Difficulty: 中等 (Medium)
分类 / Category: 图论数据结构 (Graph Data Structure)
时间复杂度 / Time Complexity: O(α(n))（α为反阿克曼函数，近似常数）
空间复杂度 / Space Complexity: O(n)
📖 算法简介 / Introduction
并查集（Union Find / Disjoint Set Union）是一种高效处理不相交集合合并与查询的数据结构。并查集支持两种核心操作：合并（Union）和查询（Find），常用于处理图的连通性、集合合并等问题。
Union Find (Disjoint Set Union, DSU) is a data structure that efficiently manages a collection of disjoint sets, supporting two main operations: union (merging two sets) and find (determining which set an element belongs to). It’s commonly used for connectivity problems and set merging.
💡 算法原理 / Principle
并查集的核心思想是用树形结构表示集合：
- 每个元素是一个节点，初始时父节点指向自己
- Find 操作：查找元素的根节点（代表元素所在集合）
- Union 操作：合并两个集合，将一个集合的根指向另一个集合的根
- 路径压缩：Find 时将路径上的节点直接指向根，减少后续查询时间
- 按秩合并：合并时让小树挂在大树下，保持树的平衡
核心思想：Each set is represented as a tree, with the root being the representative of the set. Union makes one root point to another; Find traces parent pointers to the root. Path compression and union by rank ensure near-constant time operations.
🔑 关键概念 / Key Concepts
| 概念 | 说明 |
|---|---|
| 父指针 (Parent) | 每个节点指向其父节点，根节点指向自己 |
| 根节点 (Root) | 代表集合的节点，无父或父指向自己 |
| 路径压缩 (Path Compression) | Find 时将路径上的节点直接指向根 |
| 按秩合并 (Union by Rank) | 合并时小树挂大树下，保持平衡 |
| 反阿克曼函数 (α(n)) | Ackermann 函数的反函数，近似常数 |
| 连通分量 (Connected Components) | 图中互相连通的节点集合 |
📝 代码实现 / Implementation
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * 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):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False # 已经在同一集合
# 按秩合并
if self.rank[root_x] < self.rank[root_y]:
root_x, root_y = root_y, root_x
self.parent[root_y] = root_x
if self.rank[root_x] == self.rank[root_y]:
self.rank[root_x] += 1
self.count -= 1
return True
def connected(self, x, y):
return self.find(x) == self.find(y)
# 示例
uf = UnionFind(10)
uf.union(0, 1)
uf.union(1, 2)
uf.union(3, 4)
uf.union(1, 3)
print(uf.connected(0, 4)) # True (0-1-2 和 1-3-4 连通)
print(uf.connected(0, 5)) # False
print(uf.count) # 5 (原本10个，合并后减少5个)
# 带权并查集 - 扩展
class WeightedUnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.weight = [1.0] * n # 权重
def find(self, x):
if self.parent[x] != x:
root = self.find(self.parent[x])
self.weight[x] *= self.weight[self.parent[x]]
self.parent[x] = root
return self.parent[x]
def union(self, x, y, w):
# w = weight[x] / weight[y]
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return
self.parent[root_y] = root_x
self.weight[root_y] = self.weight[x] / (w * self.weight[y])
✨ 示例 / Example
初始化（10个独立元素）：
parent: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
rank: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
执行 union(0,1), union(1,2), union(3,4), union(1,3)：
最终状态（路径压缩后）：
parent: [0, 0, 0, 0, 3, 5, 6, 7, 8, 9]
rank: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
树结构：
0 (rank=1)
/ \
1 3
| |
2 4
🎯 应用场景 / Applications
- 图的连通分量 — 判断图中节点是否连通
- 最小生成树 — Kruskal 算法核心组件
- 社交网络好友圈 — LeetCode 朋友圈问题
- 岛屿数量 — 网格连通性问题
- 字符串连接 — 判断字符串是否能连成环
- 食物链 — 带权并查集维护关系
- 等价类划分 — 合并等价元素的分组
📊 复杂度分析 / Complexity Analysis
| 操作 | 普通实现 | 路径压缩 + 按秩合并 |
|---|---|---|
| Find | O(n) | O(α(n)) ≈ O(1) |
| Union | O(n) | O(α(n)) ≈ O(1) |
| 空间 | O(n) | O(n) |
α(n) 为反阿克曼函数，增长极慢，对于 n < 10^600 几乎都小于 5
🏠 实战例题 / Practice Problems
- LeetCode 200 - 岛屿数量 - 中等
- LeetCode 547 - 省份数量（朋友圈） - 中等
- LeetCode 721 - 账户合并 - 中等
- LeetCode 684 - 冗余连接 - 中等
- LeetCode 1319 - 连通网络操作次数 - 中等
| *本文由 AI 自动生成 | Generated by AI* |