【模板】并查集

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int n,m,z,x,y;
int fa[N];
int find(int x){if(fa[x]==x)return x;return fa[x]=find(fa[x]);
}
void unionset(int x,int y){fa[find(x)]=fa[(find(y))];
}
void solve(){cin>>n>>m;for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<=m;i++){cin>>z>>x>>y;if(z==1)unionset(x,y);else {if(find(x)==find(y))cout<<"Y"<<endl;else cout<<"N"<<endl;}}
}
int main(){ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}

[蓝桥杯 2017 国 C] 合根植物

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int m,n,k,a,b,fa[N];
int find(int x){if(fa[x]==x)return x;return fa[x]=find(fa[x]);
}
void unionset(int x,int y){fa[find(x)]=fa[find(y)];
}
void solve(){cin>>m>>n;for(int i=1;i<=m*n;i++)fa[i]=i;cin>>k;for(int i=1;i<=k;i++){cin>>a>>b;unionset(a,b);}int ans=0;for(int i=1;i<=m*n;i++){if(fa[i]==i)ans++;}cout<<ans<<endl;
}
int main(){ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t;// cin>>t;t=1;while(t--)solve();return 0;
}

一中校运会之百米跑

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+10;
int n,m,k;
map<string,string>fa;
string find(string x){if(fa[x]==x)return x;return fa[x]=find(fa[x]);
}
void unionset(string x,string y){fa[find(x)]=fa[find(y)];
}
void solve(){cin>>n>>m;for(int i=1;i<=n;i++){string s;cin>>s;fa[s]=s;}for(int i=1;i<=m;i++){string x,y;cin>>x>>y;unionset(x,y);}cin>>k;for(int i=1;i<=k;i++){string x,y;cin>>x>>y;if(find(x)==find(y))cout<<"Yes."<<endl;else cout<<"No."<<endl;}
}
int main(){ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t;// cin>>t;t=1;while(t--)solve();return 0;
}

[CCC2022 S2] Good Groups

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,g;
string nx[N][2],my[N][2];
map<string,int>fa;
void solve(){cin>>n;for(int i=1;i<=n;i++)cin>>nx[i][0]>>nx[i][1];cin>>m;for(int i=1;i<=m;i++)cin>>my[i][0]>>my[i][1];cin>>g;for(int i=1;i<=g;i++){string x,y,z;cin>>x>>y>>z;fa[x]=fa[y]=fa[z]=i;}int ans=0;for(int i=1;i<=n;i++)if(fa[nx[i][0]]!=fa[nx[i][1]])ans++;for(int i=1;i<=m;i++)if(fa[my[i][0]]==fa[my[i][1]])ans++;cout<<ans<<endl;
}
int main(){ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t;// cin>>t;t=1;while(t--)solve();return 0;
}