并查集
一.简介
并查集是一种可以动态维护若干个不重叠的集合,并支持合并与查询的数据结构。它擅长动态维护许多具有传递性的关系。
一般使用树形结构存储,一般使用递归建树,这里讨论的也是树形的并查集。
在并查集中,我们使用”代表元”法,即为每个集合选定一个固定的元素作为整个集合的代表同时也是整棵树的树根,好写而巧妙。
二.基本操作
0.$Init$ , 建树与初始化(开数组并初始化)
1.$Get$ , 查询一个元素属于哪一个集合(或者说树)
从并查集树中该元素的位置不断往上查找找到根节点,该根节点则为并查集的代表元素即可知道该元素所属集合
2.$Merge$ , 把两个集合合并成一个大集合(或者说树)
首先找到第一个集合的最终祖先 , 将它指向第二个集合的根节点从而达到合并两个集合的目的
三.优化操作
注意到如果单纯建树每次查询需要沿着树干一直找到树根效率较低,最慢的时候即当树退化成一条链时单次查询
甚至需要$O(n)$的复杂度,因此我们可以对并查集进行优化
1.路径压缩——$Get$时的优化技巧
在一些题目中,我们只关心每个集合对应树的根节点是多少,并不关心这棵树的形态 , 因此可以在
每次执行Get操作的同时把访问过的每个节点(也就是所查询元素的全部祖先)都直接指向树根,即
tree[x] = get(tree[x]);也可以和返回值合并起来如
if(x == tree[x]) return x;
return tree[x] = get(tree[x]);这种方法优化后的并查集每次$Get$操作的均摊复杂度为$O(logN)$
2.按秩合并——$Merge$时的优化技巧
在一些题目中由于可能对父节点有记录的需求因此无法使用路径压缩,这时我们可以使用按秩合并
,按秩合并的实际意义其实是将树的形态变得更均衡。其思路为为每个并查集设定一个”秩”作为树大
小的代表存储在根节点上,这个”秩”可以是并查集未路径压缩前树的深度也可以是树的大小。在每次合
并两个并查集时候通过”秩”来判断两棵树的大小并将小的合并到大的里面。(一般用一个数组存秩)
需要改动的地方
- 定义一个rank[]数组存储秩
- 初始化时需要初始化每个并查集秩为0
- 合并并查集之前先比较秩大小,合并的时候将秩小的合并到大的里面(即把秩小的的根节点指向秩大的根节点)
3.我 全 都 要——码力极佳不嫌麻烦の大佬的选择
同时使用路径压缩和按秩合并时的复杂度可低到$O(\alpha(N))$
其中$\alpha(N)$为反阿克曼函数,值得一提的是它比对数函数$\log N$的增长速度还要慢,可以视为常数复杂度
因此大部分情况下其实只用路径压缩省事也够用但是特殊情况还是需要用按秩合并因此还是学会比较好=-=
四.模板代码
/*全局变量定义内容*/
int tree[N];//存并查集
int rank[N];//按秩合并特供
/*函数定义内容*/
/*Get*/
int get(int x){//查询x(递归+三元运算符做法)
/*二选一*/
return tree[x] == x ? x : tree[x]=get(tree[x]);//路径压缩
return tree[x] == x ? x : get(tree[x]);//非路径压缩
}
/*Merge*/
void merge(int x,int y){//无按秩合并版
tree[get(x)] = get(y);
}
void merge_(int x,int y){//按秩合并(秩视作树的大小)
x=get(x);y=get(y);//先全换成根节点
if(rank[x]>rank[y]){
/*若y小则将y合并到x*/
tree[y] = x;
rank[x] += rank[y];
}
else{
/*若x小则将x合并到y*/
tree[x] = y;
rank[y] += rank[x];
}
}
void merge__(int x,int y){//按秩合并(秩视作树的深度)
x=get(x);y=get(y);//先全换成根节点
if(rank[x]>rank[y]){
/*若y小则将y合并到x*/
tree[y] = x;
//深度肯定不会超过rank[x]
}
else{
/*若x小则将x合并到y*/
tree[x] = y;
rank[y] = max(rank[x]+1,rank[y]);//相等的情况会变多一层
}
}
/*main函数内内容*/
for(int i = 1; i <= n; i++ ){//初始化
tree[i] = i;
rank[i] = 0;//按秩合并特供
}
