一、啥是并查集
并查集主要用来解决集合的合并与查询问题。
把“并查集”三个字拆开看：
- 并：合并，把两个集合合并成一个。
- 查：查询，查两个元素是否在同一个集合里。
- 集：集合，一开始每个元素自己是一个集合。
用 far[i] 表示元素 i 的祖宗。如果 far[i]==i，说明 i 就是根节点。
在判断连通性等问题中可以使用并查集来解决。
二、参考代码
#include<bits/stdc++.h>
using namespace std;
int n,m,p,far[200005];
int find(int x){
if(x==far[x])return x;
return far[x]=find(far[x]);//路径压缩
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)far[i]=i;//初始化
while(m--){
int z,x,y;
cin>>z>>x>>y;
if(z==1){//合并
x=find(x),y=find(y);
far[x]=y;
}else{//查询
if(find(x)==find(y))cout<<"Y\n";
else cout<<"N\n";
}
}
return 0;
}
暂无评论