并查集模板:
#include<bits/stdc++.h> #define Maxsize 100005//只需要改这里就可以 using namespace std; int fa[Maxsize],rankk[Maxsize]; inline void init(int n)//初始化 { for(int i=1;i<=n;++i){ fa[i]=i; rankk[i]=1; } } int find(int x)//查找 { if(x==fa[x]) { return x; } else { fa[x]=find(fa[x]);//找到根节点 return fa[x]; //返回根节点 } } inline void merge(int i,int j)//合并 { int x=find(i),y=find(j);//先找到根节点的秩 if(rankk[x]<=rankk[y]){ fa[x]=y; } else{ fa[y]=x; } if(rankk[x]==rankk[y] && x!=y){ rankk[y]++; } }
#include<bits/stdc++.h> #define Maxsize 100005//只需要改这里就可以 using namespace std; int fa[Maxsize],rankk[Maxsize]; inline void init(int n)//初始化 { for(int i=1;i<=n;++i){ fa[i]=i; rankk[i]=1; } } int find(int x)//查找 { if(x==fa[x]) { return x; } else { fa[x]=find(fa[x]);//找到根节点 return fa[x]; //返回根节点 } } inline void merge(int i,int j)//合并 { int x=find(i),y=find(j);//先找到根节点的秩 if(rankk[x]<=rankk[y]){ fa[x]=y; } else{ fa[y]=x; } if(rankk[x]==rankk[y] && x!=y){ rankk[y]++; } } int main() { int n,m; cin>>n>>m; init(n); for(int i=0;i<m;i++) { int z,x,y; cin>>z>>x>>y; if(z==1) { merge(x,y); } else { if(find(x)==find(y)) cout<<"Y"<<endl; else cout<<"N"<<endl; } } return 0; }
#include<bits/stdc++.h> #define Maxsize 5005//只需要改这里就可以 using namespace std; int fa[Maxsize],rankk[Maxsize]; inline void init(int n)//初始化 { for(int i=1;i<=n;++i){ fa[i]=i; rankk[i]=1; } } int find(int x)//查找 { if(x==fa[x]) { return x; } else { fa[x]=find(fa[x]);//找到根节点 return fa[x]; //返回根节点 //以下结果一样 //return find(fa[x]); //fa[x]=find(fa[x]); } } inline void merge(int i,int j)//合并 { int x=find(i),y=find(j);//先找到根节点的秩 if(rankk[x]<=rankk[y]){ fa[x]=y; } else{ fa[y]=x; } if(rankk[x]==rankk[y] && x!=y){ rankk[y]++; } } int main() { int n,m,p; cin>>n>>m>>p; init(n); for(int i=0;i<m;i++) { int x,y; cin>>x>>y; merge(x,y); } for(int i=0;i<p;i++) { int x,y; cin>>x>>y; if(find(x)==find(y)) { cout<<"Yes"<<endl; } else { cout<<"No"<<endl; } } return 0; }
标签:int,查集,namespace,init,Maxsize,find From: https://www.cnblogs.com/zcbiao/p/17489767.html