Acwing837.连通块中点的数量(裸题，并查集求连通块中点数目) [操作系统入门]

Z时代
2024-01-10
分类：综合

地址：https://www.acwing.com/problem/content/839/

只是记录个板子，不做解析。

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<iostream>
#include<vector>
usingnamespace std;
constint maxn=1e5+10,maxn2=31*maxn;
int idx=0;
int pr[maxn],num[maxn];
typedef longlong ll;
int n,m;
int find(int x)
{
if(x!=pr[x])
    {
return pr[x]=find(pr[x]);
    }
return x;
}
void add(int a,int b)
{
int fa=find(a);
int fb=find(b);
if(fa!=fb)
    {
        pr[fb]=fa;
        num[fa]+=num[fb];
    }
return ;
}
int main()
{
    cin>>n>>m;
for(int i=1;i<=n;i++)
        pr[i]=i,num[i]=1;
while(m--)
    {
char op[3];
        scanf("%s",op);
if(op[0]==‘C‘)
        {
int a,b;
            cin>>a>>b;
            add(a,b);
        }
elseif(op[1]==‘1‘)
        {
int a,b;
            cin>>a>>b;
if(a==b)
                cout<<"Yes"<<endl;
else
            {
int fa=find(a),fb=find(b);
if(fa==fb)
                    cout<<"Yes"<<endl;
else
                    cout<<"No"<<endl;
            }
        }
else
        {
int a;
            cin>>a;
            cout<<num[find(a)]<<endl;
        }
    }
}