P1536 村村通

· · 个人记录

并查集板子题，就不想说了，直接上代码：

#include<bits/stdc++.h>
#define INT128_MAX ((__int128)1<<127)-1
using namespace std;
inline __int128 read()
{
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
        {
            f=-1;
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void write(__int128 x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
    {
        write(x/10);
    }
    putchar(x%10+'0');
}
int n,m,x,y;
unordered_map<int,int>fa;
int find(int x)
{
    if(x==fa[x])
    {
        return x;
    }
    else
    {
        fa[x]=find(fa[x]);
        return fa[x];
    }
}
void merge(int x,int y)
{
    int a=find(x),b=find(y);
    fa[a]=b;
}
void init()
{
    for(int i=1;i<=n;++i)
    {
        fa[i]=i;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    while(true)
    {
        int ans=0;
        n=read();
        if(n==0)
        {
            return 0;
        }
        m=read();
        init();
        for(int i=1;i<=m;++i)
        {
            x=read(),y=read();
            merge(x,y);
        }
        for(int i=1;i<=n;++i)
        {
            if(find(i)==i)
            {
                ans++;
            }
        }
        write(ans-1);
        puts("");
    }
    return 0;
}