比赛 9.6 评测结果 AAAAAAAAAA
题目名称 宗教信仰 最终得分 100
用户昵称 djyqjy 运行时间 0.941 s
代码语言 C++ 内存使用 3.66 MiB
提交时间 2024-09-06 19:25:32
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=50010;
int n,m;
int fa[N];
int sz[N];
bool mark[N];
int ans;
int get(int x)
{
    if(fa[x]==x) return x;
    return x=get(fa[x]);
}
void merge(int a,int b)
{
    a=get(a);
    b=get(b);
    if(a==b) return;
    if(sz[a]>sz[b]) swap(a,b);
    fa[a]=b;
    sz[b]+=sz[a];
    return;
}
int main()
{
    freopen("religion.in","r",stdin);
    freopen("religion.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        fa[i]=i,sz[i]=1;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        merge(a,b);
    }
    for(int i=1;i<=n;i++)
    {
        int x=get(i);
        if(mark[x]==0) ans++;
        mark[x]=1;
    }
    printf("%d",ans);
    return 0;
}