并查集基础
一句话总结
并查集（Union Find）是二叉树结构的衍生，用于高效解决无向图的动态连通性问题，所有操作时间复杂度 O(1)。
核心要点
1. 并查集的核心价值
并查集提供以下 API：
- union(p, q)：连接节点 p 和 q，O(1)
- connected(p, q)：查询 p 和 q 是否连通，O(1)
- count()：查询当前连通分量数量，O(1)
为什么需要并查集：
- 使用邻接表/邻接矩阵 + DFS/BFS 判断连通性需要 O(V+E)
- 并查集只需一个数组，所有操作 O(1)
- 特别适合处理动态连通性问题（边逐步增加）
2. 动态连通性问题
图结构中的连通操作与查询：
- 连接操作：将节点 p 和 q 连通
- 连通查询：判断两个节点是否连通（考虑传递性）
- 统计连通分量：查询当前图中有多少连通分量
连通关系的性质：
- 自反性：节点 p 和 p 自身是连通的
- 对称性：如果 p 和 q 连通，则 q 和 p 也连通
- 传递性：如果 p 和 q 连通，q 和 r 连通，则 p 和 r 也连通
传递性使得不能简单地通过邻接表判断连通性，必须使用并查集或图遍历算法。
3. 图结构术语
- 连通分量：图结构中的极大连通子图，每个节点自身初始时都是一个连通分量
- 连接操作：将不同连通分量合并为一个
- 连通：两个节点之间存在路径（直接或间接）
4. 应用场景
- 编译器判断同一内存对象的不同变量引用
- 社交网络中的朋友圈计算
- Kruskal 最小生成树算法中的环检测
- 动态连通性问题
5. 文章定位
本文是并查集系列的基础入门：
- 不涉及具体代码实现（在后续《Union Find 算法实现及应用》中）
- 不涉及算法题运用（在《并查集经典习题》中）
- 重点介绍为什么需要并查集以及它能解决什么问题
相关概念
- 并查集：并查集完整概念页
- 图：并查集的应用场景
- 无向图：并查集专用于无向图
- 连通分量：并查集维护的核心指标
- DFS：传统连通性判断方法，复杂度 O(V+E)
- BFS：传统连通性判断方法，复杂度 O(V+E)
- 二叉树：并查集是二叉树结构的衍生
- 多叉树：并查集本质是多叉树森林
相关实体
- labuladong：算法学习平台作者