并查集
并查集是解决"连通性"问题的利器。关键不是背代码，而是理解为什么路径压缩能让查找接近 O(1)。
面试考察点
面试官通过这道题想考察：
1. 你是否理解并查集解决什么问题
2. 你是否能解释路径压缩的原理
3. 你是否能用并查集解决实际问题
4. 你是否理解按秩合并的作用
一、什么是并查集？
1.1 问题引入
面试官追问："什么是并查集？解决什么问题？"
并查集（Union-Find）：处理"连通性"问题的数据结构
连通性问题示例：
- 社交网络：两个人是否相连？
- 朋友圈：有多少个朋友圈？
- 岛屿数量：哪些陆地是连在一起的？
核心操作：
1. Union(A, B)：把 A 和 B 合并到同一个集合
2. Find(A)：找到 A 所属集合的代表
连通性的特点：
- 自反性：A 和 A 连通
- 对称性：A 和 B 连通 → B 和 A 连通
- 传递性：A 和 B 连通，B 和 C 连通 → A 和 C 连通
1.2 并查集的核心思想
类比：帮派
init：每个人是自己帮派的帮主
Union(A, B)：把两个帮派合并
Find(A)：找到 A 的帮主
帮派 1 帮派 2
帮主 A 帮主 D
/ \ / \
B C E F
Union(A, D)：
帮主 A 和帮主 D 打一架
输的认赢的当帮主
帮派 1+2
帮主 A
/ | \
B C D
/ \
E F
Find(B) = A，表示 B 在 A 的帮派里
Find(E) = A，表示 E 也在 A 的帮派里
所以 B 和 E 是连通的！
二、并查集的实现
2.1 基本实现
并查集用数组实现：
parent[i] = i 的父节点
- 如果 parent[i] = i，说明 i 是根节点
- 通过 parent[i] 一直往上找，最终找到根
Find(A)：
def find(A):
if parent[A] != A:
return find(parent[A]) # 递归找根
return A
Union(A, B)：
def union(A, B):
rootA = find(A)
rootB = find(B)
if rootA != rootB:
parent[rootB] = rootA # 把 B 的根接到 A 的根上
2.2 路径压缩（核心优化）
面试官追问："什么是路径压缩？为什么需要？"
问题：链式结构
初始化：
parent = [0, 1, 2, 3, 4]
每个节点的父节点是自己
Union(0, 1)：parent[1] = 0
Union(1, 2)：parent[2] = 1（链式）
Union(2, 3)：parent[3] = 2
...
最终：
0 ← 1 ← 2 ← 3 ← 4
| | | | |
0 0 0 0 0
找 4 的根：
find(4) → find(3) → find(2) → find(1) → find(0) = 0
要找 4 次！
路径压缩优化：
在找根的过程中，把所有经过的节点都直接指向根：
find(4):
4 → 3 → 2 → 1 → 0（找到根）
压缩后：
0 ← 0
↑ ↑
4 → 3 → 2 → 1（都直接指向 0）
下次再找 4 的根，只需要一步！
复杂度：接近 O(1)！
2.3 按秩合并
按秩合并：把小的树接到大的树上
为什么不随意合并？
因为合并后树可能会变深，
下次 Find 就要走更多步。
按秩合并策略：
- rank[i] = i 所在树的高度
- 合并时，把矮的树接到高的树上
为什么有效？
因为树的高度不会增加超过 log n！
结合路径压缩，几乎是 O(1)。
三、面试真题讲解
3.1 朋友圈数量（LeetCode 547）
考察点：并查集的典型应用
问题：同学之间认识，问有多少个朋友圈
示例：
M = [[1,1,0],
[1,1,0],
[0,0,1]]
M[i][j] = 1 表示 i 和 j 是朋友
朋友关系是传递的！
思路：
- 每个人是一个集合
- 遍历矩阵，如果 M[i][j] = 1，Union(i, j)
- 最后数有多少个独立的集合
这就是并查集的直接应用！
3.2 岛屿数量（变种）
考察点：二维网格的连通性
问题：二维网格中，'1' 是陆地，'1' 相连形成一个岛屿
思路：
- 每个陆地格子是一个节点
- 相邻的陆地（在上下左右）相连
- 用并查集统计连通分量
但通常 BFS/DFS 更直观：
- 遍历网格
- 如果是 '1' 且未访问
- BFS/DFS 标记所有相连的 '1'
- 岛屿数 + 1
四、面试总结
并查集核心要点
┌─────────────────────────────────────────────────┐
│ 并查集核心 │
├─────────────────────────────────────────────────┤
│ │
│ 解决的问题：连通性 │
│ │
│ 核心操作： │
│ - Find：找根节点 │
│ - Union：合并集合 │
│ │
│ 优化： │
│ - 路径压缩：让查找几乎 O(1) │
│ - 按秩合并：避免树变深 │
│ │
│ 时间复杂度： │
│ - 近乎 O(1)，准确说是 α(n)（Ackermann 反函数）│
│ │
└─────────────────────────────────────────────────┘
面试能加分的回答
1. 能解释路径压缩
"在找根的过程中，把所有节点直接指向根，
下次找就快了"
2. 能解释按秩合并
"把矮的树接到高的树上，
保证树的高度不会太大"
3. 能说出应用场景
"连通性问题、朋友圈、岛屿数量、检测环"
相关题目
- LeetCode 547 - 省份数量 - 并查集基础
- LeetCode 200 - 岛屿数量 - BFS/DFS