并查集
在每个集合中选择一个元素，作为整个集合的代表。使用一个树形结构存储每个集合，树上的每个节点都是一个元素，树根是集合的代表元素。
存储时，记录每个节点 \(x\) 的父亲 \(fa[x]\) 。查询 \(x\) 和 \(y\) 是否在同一集合时，分别从两个点出发，寻找它们的树根。若树根相同，则说明 \(x\) 和 \(y\) 在同一个集合中。
容易发现，在某种特殊情况下，该树形结构会退化成链，此时在链上寻找，复杂度退化为 \(O(n)\) ，需要优化。
路径压缩和按秩合并
路径压缩：每次查找时把访问过的每个节点指向树根，这样就避免了树退化成链。每次查询的均摊复杂度为 \(O(log n)\) 。
按秩合并：把小的结构合并到大的结构当中，又叫启发式合并。每次查询的均摊复杂度为 \(O(log n)\) 。因为保留了原有的结构，常用于可持久化中。
例题
#include <bits/stdc++.h>
using namespace std;
const int N=1e4+5;
int n,m,fa[N];
int find(int x){
// printf("%d %d\n",x,fa[x]);
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
x=find(x),y=find(y);
fa[x]=y;
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i) fa[i]=i;
int opt,x,y;
while(m--){
scanf("%d %d %d",&opt,&x,&y);
if(opt==1) merge(x,y);
else{
x=find(x),y=find(y);
if(x==y) puts("Y");
else puts("N");
}
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,fa[1005],L,R=1e9,ans=1e9;
struct node{
int x,y,t;
}a[N];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
x=find(x),y=find(y);
fa[x]=y;
}
bool chk(int x){
for(int i=1;i<=n;++i) fa[i]=i;
for(int i=1;i<=m;++i){
if(a[i].t>x) continue;
merge(a[i].x,a[i].y);
}
for(int i=2;i<=n;++i){
if(find(i)!=find(i-1)) return 0;
}
return 1;
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=m;++i){
scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].t);
}
while(L<=R){
int mid=L+R>>1;
if(chk(mid)) R=mid-1,ans=mid;
else L=mid+1;
}
if(ans==1e9) printf("-1");
else printf("%d",ans);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,fa[N],a[N],cnt;
vector<int> edge[N];
string ans[N];
bool vis[N];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){
scanf("%d %d",&n,&m);
int x,y;
for(int i=1;i<=m;++i){
scanf("%d %d",&x,&y);
edge[x].push_back(y);
edge[y].push_back(x);
}
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
fa[i]=i;
}
for(int i=n;i>=1;--i){
vis[a[i]]=1;
cnt++;
for(int j=0;j<edge[a[i]].size();++j){
x=a[i],y=edge[x][j];
if(!vis[y]) continue;
x=find(x),y=find(y);
if(x==y) continue;
fa[x]=y;
cnt--;
}
ans[i]=cnt==1?"YES":"NO";
}
for(int i=1;i<=n;++i){
cout<<ans[i]<<endl;
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N=505;
int n,m,fa[N*N][2],ans0,ans1,a[N][N];
int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};
int id(int i,int j){
return (i-1)*n+j;
}
int find(int x,int i){
return fa[x][i]==x?x:fa[x][i]=find(fa[x][i],i);
}
void merge(int x,int y){
for(int i=1;i<=4;++i){
int xx=x+dx[i],yy=y+dy[i];
if(xx<1 || xx>n || yy<1 || yy>n) continue;
if(a[xx][yy]!=a[x][y]) continue;
if(find(id(xx,yy),a[x][y])==find(id(x,y),a[x][y])) continue;
if(a[x][y]==0) ans0--;
else ans1--;
fa[find(id(xx,yy),a[x][y])][a[x][y]]=find(id(x,y),a[x][y]);
}
}
int main(){
scanf("%d %d",&n,&m);
memset(a,-1,sizeof(a));
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
fa[id(i,j)][0]=fa[id(i,j)][1]=id(i,j);
}
}
int c,x,y;
while(m--){
scanf("%d %d %d",&c,&x,&y);
if(c==0) ans0++; //白
else ans1++; //黑5
a[x][y]=c;
merge(x,y);
printf("%d\n",ans1+ans0);
}
return 0;
}
发现存在一个集合 \(A\) ，使得若下一个数 \(a_i \in A\) 则 \(a_i\) 会变成一个值，集合 \(A\) 中的任意一个值再次出现都会变为一个确定的值，可以用并查集维护这种传递性。
用并查集中的树根记录最小的未出现的数，对于每个 \(a_i\) 都会变为 \(find(a_i)\) ，这时 \(find(a_i)\) 也出现过了，于是让 \(find(a_i)\) 加1。
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,a,fa[N];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){
scanf("%d",&n);
for(int i=1;i<N;++i){
fa[i]=i;
}
for(int i=1;i<=n;++i){
scanf("%d",&a);
a=find(a);
fa[a]=a+1;
printf("%d ",a);
}
//find(a)可以找到最小的未出现的数
//下回出现重复的数后，直接find到父亲即可
return 0;
}
对于一段已经被染色的区间 \([L,R]\) 可以让其中每个点的 \(fa\) 都指向它的左端点，这样一旦到达这个区间上一点就可以用并查集 \(find\) 到左端点，从而实现“跳跃”的操作。
对于每次操作，我们可以让右端点不断向左“跳跃”，从而排除已经被记录的白点。
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,fa[N],cnt;//cnt计算白色点个数
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i){
fa[i]=i;
}
int L,R;
while(m--){
scanf("%d %d",&L,&R);
while(L<=R){
R=find(R);
if(R<L) break;
fa[R]=find(R-1);
cnt++;
}
printf("%d\n",n-cnt);
}
return 0;
}
“扩展域”与“边带权”的并查集
#include <bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m,fa[N<<1],ans;
char opt;
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
x=find(x),y=find(y);
fa[y]=x;
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=2*n;++i){
fa[i]=i;
}
int x,y;
//假定i的敌人是i+n
//那么若a和b是敌人，a和b+n就是朋友，b和a+n也是朋友
while(m--){
cin>>opt>>x>>y;
if(opt=='F') merge(x,y);
else merge(x,y+n),merge(y,x+n);
}
for(int i=1;i<=n;++i){
// printf("%d ",fa[i]);
if(fa[i]==i) ans++;
}
printf("%d",ans);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N=30005;
int T,sz[N],d[N],fa[N];
char opt;
int find(int x){
if(fa[x]==x) return x;
int fx=find(fa[x]);
d[x]+=d[fa[x]];
return fa[x]=fx;
}
int main(){
scanf("%d",&T);
int x,y;
for(int i=1;i<N;++i){
sz[i]=1;
fa[i]=i;
}
while(T--){
cin>>opt>>x>>y;
int fx=find(x);
int fy=find(y);
if(opt=='C'){
if(fx==fy) printf("%d\n",abs(d[x]-d[y])-1);
else printf("-1\n");
}
else{
d[fx]=sz[fy];
sz[fy]+=sz[fx];
sz[fx]=0;
fa[fx]=fy;
}
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N=30005;
int T,sz[N],d[N],fa[N];
int find(int x){
if(fa[x]==x) return x;
int fx=find(fa[x]);
d[x]+=d[fa[x]];
// printf("%d %d\n",x,d[x]);
return fa[x]=fx;
}
int main(){
scanf("%d",&T);
for(int i=1;i<N;++i){
sz[i]=1;
fa[i]=i;
}
char opt;
int x=0,y=0;
while(T--){
cin>>opt>>x;
if(opt=='C'){
find(x);
printf("%d\n",d[x]);
}
else{
scanf("%d",&y);
// printf("A %d %d\n",x,y);
int fx=find(x);
int fy=find(y);
d[fx]+=sz[fy];
sz[fy]+=sz[fx];
sz[fx]=0;
fa[fx]=fy;
}
}
return 0;
}