【算法笔记】并查集详解

🚀 并查集（Union-Find）详解：原理、实现与优化

并查集（Union-Find）是一种非常高效的数据结构，用于处理动态连通性问题，即判断若干个元素是否属于同一个集合，并支持集合合并操作。它在图算法中（如 Kruskal 最小生成树）、朋友圈统计、网络连通性判断等场景中非常常见。

🧠 并查集的核心功能

• find(x)：查找元素 x 所在集合的代表（也叫“根节点”）
• union(x, y)：将元素 x 和 y 所在的两个集合合并
• parent[x]：记录每个元素的“父亲”，通过父亲链条找祖先（树结构）

🧩 并查集基本结构

初始化时，每个元素自己是自己的父亲，表示各自是一个独立集合：

n = 5
parents = list(range(n + 1))  # parents[i] = i，0号位不使用

🔍 基本实现：find 和 union

不带路径压缩的 find

def find(x):if parents[x] == x:return xelse:return find(parents[x])

基本 union 实现

def union(x, y):root_x = find(x)root_y = find(y)if root_x == root_y:return False  # 已经在同一个集合中parents[root_y] = root_x  # 合并return True

⚡ 路径压缩优化（推荐）

def find(x):if x != parents[x]:parents[x] = find(parents[x])  # 路径压缩return parents[x]

🧠 类比记忆

• 每个元素的 parent 就像是它的“爸爸”
• find(x) 就是往上找老祖宗
• union(x, y) 就是两个家族联姻，把一个家族并进另一个

📈 时间复杂度分析

路径压缩优化后：

O(α(n))，其中 α 是反阿克曼函数，实际几乎为常数

✅ 示例测试

n = 5
parents = list(range(n + 1))def find(x):if x != parents[x]:parents[x] = find(parents[x])return parents[x]def union(x, y):px = find(x)py = find(y)if px == py:return Falseparents[py] = pxreturn Trueunion(1, 2)
union(3, 4)
union(2, 3)print(find(4))  # 应为 1
print(parents)

📚 应用场景

• Kruskal 最小生成树算法
• 网络连通性判断
• 动态连通块个数统计
• 岛屿数量（LeetCode 200）
• 冗余连接（LeetCode 684）
• 朋友圈数量（LeetCode 547）

🎯 总结

术语	含义
find(x)	找出 x 所属集合的根节点
union(x, y)	合并 x 和 y 的集合（若不属于同一集合）
路径压缩	加快 find 查询效率
树的结构	集合之间的连接关系

并查集看起来简单，背后其实是极高效的数据结构设计。建议掌握它，并尝试应用到图论、集合问题中去！

🧩 常见练习题

✅ 基础入门题

题号	题目名称	链接	简介
200	岛屿数量	LeetCode 200	判断二维网格中有多少个连通块
684	冗余连接	LeetCode 684	找出图中导致环的边
1319	连通网络的操作次数	LeetCode 1319	判断有多少连通块，以及最少连接次数

---

🧠 中级应用题

题号	题目名称	链接	简介
1202	交换字符串中的元素	LeetCode 1202	使用并查集形成交换组，对组内排序
721	账户合并	LeetCode 721	通过邮箱合并属于同一用户的账户
323	无向图中连通分量的数目	LeetCode 323	通用连通块计数问题

---

🔍 进阶与变种题

题号	题目名称	链接	简介
399	除法求值	LeetCode 399	带权并查集：维护节点之间的比例关系
547	省份数量（等价朋友圈问题）	LeetCode 547	判断有多少朋友圈/省份
990	等式方程的可满足性	LeetCode 990	并查集维护等式约束

---

📌 推荐练习顺序

1. 200 - 岛屿数量
2. 684 - 冗余连接
3. 1319 - 连通网络的操作次数
4. 547 - 省份数量
5. 1202 - 字符串交换
6. 721 - 邮箱合并
7. 399 - 除法求值
8. 990 - 等式方程可解性

---

🧠 建议掌握：

• 基础并查集结构（find, union）
• 路径压缩优化
• 带权并查集（维护差值、比例等信息）
• 一维映射（如坐标 → 编号）