并查集
并查集是一种图形数据结构,用于存储图中结点的连通关系。
每个结点有一个父亲,可以理解为“一只伸出去的手”,会指向另外一个点,初始时指向自己。
一个点的根节点是该点的父亲的父亲的的父亲,直到某个点的父亲是自己 根
当两个点的根相同时,我们就说他们是属于同一类,或者说是连通的。
如下:7、5、1、3、6的根都是3,所以他们是连通的,2、4是连通的,而2、6不连通,因为他们的根不 同
找根
找根的方法是:
如果当前点不是根,就返回父亲的根。否则就是自己。
用递归的方法实现
int root(int x){
if(pre[x]==x)return x;
return root(pre[x]);
}
合并
在并查集中,所有的操作都在根上,假如我要使得x和y两个点合并,只需要将root(x)指向 root(y),或使得root(y)指向root(x)。 pre[root(x)]= root(y);
例如我要合并4和6.则需要将2指向3或将3指向2.
路径压缩
找根函数的复杂度最坏情况下会达到O(n),如果查询次数较多的话效率将会非常低下。
我们可以在找根的过程中,将父亲直接指向根,从而实现路径压缩,这样可以使得找根的总体时间复杂度接近O(1)。如下图,执行一次root(7)之后,沿途的点都会直接指向根3。
int root(int x){
return pre[x] = (pre[x]==x?x:root(pre[x]));
}
蓝桥幼儿园
#include<iostream>
using namespace std;
const int N = 2e5+9;
int pre[N],n,m;
int root(int x){
pre[x] = (pre[x]==x)?x:root(pre[x]);
return pre[x];
}
int main( ){
cin>>n>>m;
for(int i=1;i<=n;i++)pre[i]=i;
while(m--){
int op,x,y;
cin>>op>>x>>y;
if(op==1){
pre[root(x)]=root(y);
}else{
if(root(x)==root(y))cout<<"YES"<<'\n';
else cout<<"NO"<<'\n';
}
}
return 0;
}
修改数组
思路:并查集的查询修改特性,根是未重复的数,非根是重复的数。初始化并查集 pre[i]=i表示每个根都未重复,遍历数组 a,遍历到 x 时将 x 修改为root(x) 的根,将 root(x) 指向 root(x+1) 的根,表示 x 的过去根已经重复,新根未重复。
#include<iostream>
using namespace std;
const int N = 1e6+10;
int a[N],pre[N];
int root(int x){
return pre[x] = (pre[x]==x)?x:root(pre[x]);
}
int main( ){
int n;cin>>n;
for(int i=1;i<=N;i++)pre[i]=i;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i] = root(a[i]);
pre[a[i]] = root(a[i]+1);
}
for(int i=1;i<=n;i++)cout<<a[i]<<" \n"[n==i];
return 0;
}