题解 | #畅通工程#

#include <iostream>

using namespace std;

const int N = 1010;

int p[N];
int height[N];

void init(int n){
    for(int i=1;i<=n;i++)p[i]=i,height[i]=0;
}

int find(int a){
    if(a!=p[a])p[a]=find(p[a]);
    return p[a];
}

void cUnion(int a, int b){
    int x = find(a);
    int y = find(b);
    if(x!=y){
        if(height[x]>height[y]){
            p[y]=x;
        }else if(height[x]<height[y]){
            p[x]=y;
        }else{
            p[x]=y;
            height[y]+=height[x];
        }
    }
}

int main() {
    int n,m;
    while(cin>>n>>m){
        init(n);
        while(m--){
            int a,b;
            cin>>a>>b;
            cUnion(a, b);
        }
        int ans=-1;
        for(int i=1;i<=n;i++){
            if(p[i]==i)ans++;
        }
        cout<<ans<<endl;
    }


}