题目列表 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
模板
836. 合并集合 - AcWing题库
#include<bits/stdc++.h>
using ll=long long;
//#define int ll
const int N=1e5+10,mod=1e9+7;
int n,m;
int p[N],sz[N];
int find(int a)
{
if(p[a]!=a) p[a]=find(p[a]);
return p[a];
}
void merge(int a,int b)
{
int pa=find(a),pb=find(b);
if(pa!=pb){
p[pa]=pb;
sz[pb]+=sz[pa];
}
}
void que(int a,int b){
if(find(a)==find(b)) std::cout<<"Yes"<<'\n';
else std::cout<<"No"<<'\n';
}
void solve()
{
std::cin>>n>>m;
for(int i=1;i<=n;i++)
{
sz[i]=1;
p[i]=i;
}
while(m--)
{
char op;
int a,b;
std::cin>>op>>a>>b;
if(op=='M')
{
merge(a,b);
}else{
que(a,b);
}
}
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int t=1;
//std::cin>>t;
while(t--)
{
solve();
}
return 0;
}
837. 连通块中点的数量 - AcWing题库
#include<bits/stdc++.h>
const int N=1e5+10;
int p[N];
int size[N];
int find(int x)
{
if(x!=p[x])
{
p[x]=find(p[x]);
}
return p[x];
}
void merge(int a,int b)
{
int pa=find(a),pb=find(b);
if(pa!=pb)
{
p[pa]=pb;
size[pb]+=size[pa];
}
}
void query(int a,int b)
{
int pa=find(a),pb=find(b);
if(pa==pb)
{
std::cout<<"Yes"<<'\n';
}else std::cout<<"No"<<'\n';
}
void solve()
{
int n,m;
std::cin>>n>>m;
for(int i=1;i<=n;i++)
{
p[i]=i;
size[i]=1;
}
while(m--)
{
char op[5];
std::cin>>op;
int a,b;
if(op[0]=='C')
{
std::cin>>a>>b;
merge(a,b);
}else if(op[1]=='1'){
std::cin>>a>>b;
query(a,b);
}else{
std::cin>>a;
//询问a中连通块点的个数
std::cout<<size[find(a)]<<'\n';
}
}
}
signed main()
{
int t=1;
//std::cin>>t;
while(t--)
{
solve();
}
return 0;
}240. 食物链 - AcWing题库
普及-
（合并集合）（P2256 一中校运会之百米跑 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
判断点是否在一个集合中。
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
#define fir first
#define sec second
#define int ll
const int N=2e4+10;
const int mod=1e9+7;
const double eps=1e-6;
int n,m;
int p[N],sz[N];
ll find(int a)
{
if(p[a]!=a) p[a]=find(p[a]);
return p[a];
}
void merge(int a,int b)
{
int pa=find(a),pb=find(b);
if(pa!=pb)
{
p[pa]=pb;
sz[pb]+=sz[pa];
}
}
bool que(int a,int b)
{
if(find(a)==find(b)) return true;
else return false;
}
void solve()
{
std::cin>>n>>m;
std::map<std::string,int> mp;
for(int i=1;i<=n;i++)
{
std::string s;
std::cin>>s;
mp[s]=i;
p[i]=i,sz[i]=1;
}
for(int i=1;i<=m;i++)
{
std::string a,b;
std::cin>>a>>b;
merge(mp[a],mp[b]);
}
int k;
std::cin>>k;
while(k--)
{
std::string a,b;
std::cin>>a>>b;
if(que(mp[a],mp[b])) std::cout<<"Yes.\n";
else std::cout<<"No.\n";
}
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int t=1;
//std::cin>>t;
while(t--)
{
solve();
}
return 0;
}（合并集合）P8396 [CCC2022 S2] Good Groups - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
还是个模板题
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
#define fir first
#define sec second
//#define int ll
const int N=1e5+10;
const int mod=1e9+7;
int n;
ll ans;
struct node{
std::string s1,s2;
}a[N];
struct nod{
std::string s1,s2;
}b[N];
std::unordered_map<std::string,std::string> p;
std::string find(std::string& s)
{
if(p[s]!=s) p[s]=find(p[s]);
return p[s];
}
void merge(std::string& a,std::string& b)
{
std::string pa=find(a),pb=find(b);
if(pa!=pb)
{
p[pa]=pb;
}
}
bool que(std::string& a,std::string& b)
{
if(find(a)!=find(b)) return false;
else return true;
}
void solve()
{
int x;
//每个组3个人
std::cin>>x;
// getchar();
for(int i=1;i<=x;i++)
{
//getchar();
std::cin>>a[i].s1>>a[i].s2;
}
int y;
std::cin>>y;
for(int i=1;i<=y;i++)
{
//getchar();
std::cin>>b[i].s1>>b[i].s2;
}
int g;
std::cin>>g;
for(int i=1;i<=g;i++)
{
std::string a,b,c;
//getchar();
std::cin>>a>>b>>c;
if(p.count(a)==0) p[a]=a;
if(p.count(b)==0) p[b]=b;
if(p.count(c)==0) p[c]=c;
merge(a,b);
merge(c,b);
}
ll ans=0;
for(int i=1;i<=x;i++)
{
if(!que(a[i].s1,a[i].s2)) ans++;
}
for(int i=1;i<=y;i++)
{
if(que(b[i].s1,b[i].s2)) ans++;
}
std::cout<<ans<<'\n';
}
signed main()
{
//freopen("a","w",stdout);//把结果输出到a.in里面
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int t=1;
//std::cin>>t;
while(t--)
{
solve();
}
return 0;
}
