题解 | #畅通工程#

#include <iostream>
using namespace std;
const int maxn=1000;
int father[maxn];
int height[maxn];
void init(){
    for(int i=0;i<maxn;i++){
        father[i]=i;
    }
}
int findfather(int x){
    if(father[x]!=x) father[x]=findfather(father[x]);
    return father[x];
}
void Union(int x,int y){
	x=findfather(x);
	y=findfather(y);
    if(x==y) return;
    else if(height[x]<height[y]) father[x]=y;
    else if(height[x]>height[y]) father[y]=x;
    else{
        father[y]=x;
        height[x]++;
    }
}
int main() {
    int n,m;
    while(cin>>n>>m){
        init();
        for(int i=0;i<m;i++){
            int a,b;
            cin>>a>>b;
            int f1=findfather(a);
            int f2=findfather(b);
            if(f1!=f2){
            Union(a,b);
            }
        }
        int l=0;
        for(int i=1;i<=n;i++){
            if(father[i]==i) l++;
        }
        cout<<l-1<<endl;


    }
}