并查集（Union Find）
定义
并查集（Union Find）是二叉树结构的衍生，用于高效解决无向图的连通性问题。它可以在 O(1) 时间内完成合并、查询和统计操作，且只需一个数组实现，无需构建完整的图结构（邻接表/邻接矩阵）。
核心操作（API）
class UF {
// 初始化并查集，包含 n 个节点，时间复杂度 O(n)
public UF(int n);
// 连接节点 p 和节点 q，时间复杂度 O(1)
public void union(int p, int q);
// 查询节点 p 和节点 q 是否连通，时间复杂度 O(1)
public boolean connected(int p, int q);
// 查询当前的连通分量数量，时间复杂度 O(1)
public int count();
}
动态连通性问题
并查集解决的核心问题：
- 连接操作：将图中的两个节点连通
- 连通查询：判断两个节点是否连通（考虑传递性）
- 统计连通分量：查询当前图中共有多少个连通分量
连通关系的性质：
- 自反性：节点 p 和 p 自身是连通的
- 对称性：如果节点 p 和 q 连通，那么 q 和 p 也连通
- 传递性：如果 p 和 q 连通，q 和 r 连通，那么 p 和 r 也连通
传递性是连通关系的核心特性，使得不能简单地通过邻接表判断连通性，必须使用并查集或图遍历算法。
为什么需要并查集
传统方法使用 DFS/BFS 遍历判断连通性：
- connected 方法：需要 O(V+E) 时间进行图遍历
- count 方法：需要 O(V+E) 时间遍历整幅图统计连通分量
并查集的优势：
- 所有操作均为 O(1) 时间复杂度
- 不需要构建图结构，只需一个 parent 数组
- 适合处理动态连通性问题（边逐步增加的情况）
应用场景
- 判断无向图的连通性
- Kruskal 最小生成树算法中的环检测
- 动态连通性问题（如编译器判断同一内存对象的不同引用）
- 社交网络中的朋友圈计算
- 森林中多棵树的根节点管理（如 N 叉树森林）