引入
并查集是一种用于维护集合的数据结构,实现为一个森林。
其中每一棵独立的树表示一个集合,树中的每个节点一一对应集合中的每一个元素
功能
顾名思义,它支持高效的合并集合,查询某元素所属集合两种操作
(注意:并查集无法以较低复杂度实现集合的分离)
1:合并:将两个集合合并为同一个集合
2:查询:返回某元素所属集合
数据表示
一个节点代表一个元素
元素的值在数组中以下标的形式储存(类似于桶排序)
int fa[N]
存放整个森林的每一个节点的父节点下标
fa[x]=y
表示节点x的父节点是节点y(自然x,y同属一个集合)
比如:
fa[1]=1,fa[2]=1,fa[3]=1,fa[4]=3,fa[6]=4
需要注意的是:在根节点指向自己,表示集合结束
初始化
在一系列合并操作之前的初始状态中,无法得知每个元素的从属关系
一共n个元素,我们需要让每个元素自成一个集合(每个节点都是根节点),共有n个集合
即让每个节点指向它自己
for(int i=1;i<=n;i++) fa[i]=i;
查询操作及其优化
朴素查询
因为我们把根节点元素看作该集合的代表
所以我们想知道某元素的所属集合,只需要知道根节点元素是什么
我们查询某元素的父节点就可以一直查询直到找到根节点
1:如果参数的父节点等于自己,说明参数为根节点,返回参数值
2:如果参数的父节点不等于自己,继续递归地查找参数的父节点
int find(int x){
if(fa[x]==x) return x;
return find(fa[x]);
}
举个例子:查找6的根节点
路径压缩优化
当集合的深度越来越长时,我们递归查找深度越来越大,所耗费的时间越来越大
因此我们需要想办法减小集合树的深度
当我们完成一整个查询操作时,因为需要遍历这条路径上的所有节点
当我们开始回溯时,因为我们此时已经得知了根节点,原路返回时顺便将所有节点直接指向根节点
如图:查找6的根节点时,我们在回溯时顺便将节点1,3,4,6
指向了根节点1
(实际上只修改了4和6,1和3原来本身就是指向1的)
注意:我们没有回溯时的路径1->3->4->6并没有遍历5,所以5还是维持原样
最后代码只有一点不同:
int find(int x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);//返回根节点的值时顺便赋给x的父节点下标,有点像记忆化递归
}
合并操作及其优化
朴素合并:
将元素x所在集合的根节点指向元素y所在集合的根节y点
void unionset(int x,int y){
if(find(x)==find(y)) return;//x,y同属一个集合,不做合并操作
fa[find(x)]=find(y);//合并时需要查询根节点,会顺便完成路径优化操作
}
比如unionset(6,9):将6所在集合的根节点1指向9所在集合的根节点7
启发式合并优化
合并时,选择哪棵树的根节点作为新树的根节点会影响未来操作的复杂度。我们可以将节点较少或深度较小的树连到另一棵,以免发生退化。
vector<int> siz(N,1);//记录集合中节点数量,初始化为1(并查集初始化时每个节点都是一个集合)
void unionset(int x,int y){
x=find(x),y=find(y);//引入中间变量x,y
if (x==y) return;
if (siz[x]>siz[y]) swap(x, y);//如xiaoji果x所属集合的节点个数大于y,交换x,y中间变量的值
fa[x]=y;//保证了一定是较小的集合指向较大的集合
siz[y]+=siz[x];//更新较大集合的数量
}
算法竞赛中并查集的路径优化已经足够优秀,足以把操作降至O(1) 因此我们一般只用路径压缩就足够了
由于路径压缩单次合并可能造成大量修改,有时路径压缩并不适合使用。例如,在可持久化并查集、线段树分治 + 并查集中,一般使用只启发式合并的并查集。
AcWing 836. 合并集合https://www.acwing.com/problem/content/838/
统计集合中点的数量
启发式合并中的siz数组中:siz[find(a)]
表示节点a所属集合的节点数
AcWing 837. 连通块中点的数量https://www.acwing.com/problem/content/839/
带权并查集
AcWing 240. 食物链 https://www.acwing.com/problem/content/242/
种类并查集
。。。