并查集 Union-Find
高效追踪连通分量 — 就像通过朋友关系分组
概念
现实类比
** 社交网络**：两个人成为朋友后，他们的朋友圈合并。并查集追踪每个人属于哪个组，快速回答"这两个人是否相连？"
核心操作
| 操作 | 说明 | 时间 |
|---|---|---|
| find(x) | 查找 x 的根 | O(α(n)) |
| union(x, y) | 合并 x 和 y 所在的集合 | O(α(n)) |
| connected(x, y) | 检查 x 和 y 是否在同一集合 | O(α(n)) |
优化
- 路径压缩：
find时让所有节点直接指向根 - 按秩合并：矮树挂到高树下
面试题
省份数量
LeetCode 547：计算朋友圈（连通分量）数量
决策指南
| 场景 | 推荐 |
|---|---|
| 动态连通性追踪 | 并查集 |
| 需要合并集合并查询 | 并查集 |
| 小型静态数据集 | 数组或 Set 即可 |