1.定义
-
并查集是一种树型的数据结构,用于处理一些不相交集合(disjoint sets)的合并及查询问题。
-
并查集通常包含两种操作
- 查找(Find):查询两个元素是否在同一个集合中
- 合并(Union):把两个不相交的集合合并为一个集合
2.代码
(1)初始化
|
(2)查找
//查询根结点 |
(3)合并
//合并,把 j 合并到 i 中去,就是把j的双亲结点设为i |
(4)路径压缩
减少路径长度,将集合扁平化,每个元素父节点设为根节点,提高效率
查找
//查询根结点 |
完整代码
|
(5)按秩合并
显然的,简单的树应合并到复杂的树上从而使得树的深度较小,即按秩合并的思想;
初始化
void init(int n){ |
合并
//合并 |
(6)模板代码
//并查集类 |
3.例题
|