题解

太糖了

#include<bits/stdc++.h>
using namespace std;
typedef int Vanitas;
Vanitas fa[20000],t[20000],n,m,p;
int get(int x){
    if(fa[x]==x) return x;
    return fa[x]=get(fa[x]);
}
void merge(int x,int y){
    int fx=get(x),fy=get(y);
    if(fx!=fy){
        if(t[fx]>t[fy]) fa[fy]=fx;
        else{
            fa[fx]=fy;
            if(t[fx]==t[fy])t[fy]++;
        }
    }
}
int main(){
    while(cin>>n and n){
        cin>>m;  
        for(Vanitas i=1;i<=n;i++) fa[i]=i;
        for(Vanitas i=1;i<=m;i++){
            Vanitas u,v;
            cin>>u>>v;
            if(get(u)!=get(v)) merge(u,v);
        }
        Vanitas sum=0;
        for(Vanitas i=1;i<=n;i++){
            if(fa[i]==i){
                sum++;
            }
        }
        cout<<sum-1<<endl;
    }
    return 0;
}