AcWing 837. 连通块中点的数量
原题链接
简单
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+2;
int p[N];
map<int,int> mp;
int find(int x)
{
if(p[x]!=x)
{
p[x]=find(p[x]);
}
else
{
return p[x];
}
}
int main()
{
int m,n; cin>>n>>m;
for(int i=1;i<=n;i++)
{
p[i]=i;
mp[i]=1;
}
for(int i=0;i<m;i++)
{
string s; cin>>s;
if(s=="C")
{
int l,r; cin>>l>>r;
if(find(l)!=find(r))
{
mp[find(r)]+=mp[find(l)];
p[find(l)]=find(r);
}
}
else if(s=="Q1")
{
int l,r; cin>>l>>r;
if(find(l)==find(r))
{
cout<<"Yes"<<endl;
}
else
{
cout<<"No"<<endl;
}
}
else
{
int x; cin>>x;
cout<<mp[find(x)]<<endl;
}
}
return 0;
}