题解 | #畅通工程#

并查集的实现

#include <iostream>

using namespace std;

int father[100010];
int height[100010];
void initial(int n){
    for(int i=0;i<=n;i++){
        father[i]=-1;
        height[i]=0;
    }
}

int Find(int x){
    if (father[x]==-1)return x;
    return Find(father[x]);
}
void Union(int x,int y){
    int fx=Find(x);
    int fy=Find(y);
    if (fx==fy)return;
    if(height[fx]>height[fy]){
        father[fy]=fx;
    }
    else if(height[fx]<height[fy]){
        father[fx]=fy;
    }
    else{
        father[fx]=fy;
        height[fy]++;
    }
}


int main()
{
    int n;
    int m;
    while(cin>>n>>m){
        int counts=0;
        initial(n);
        int para1,para2;
        for(int i=0;i<m;i++){
            cin>>para1>>para2;
            Union(para1,para2);
        }
        for(int i=1;i<=n;i++){
            if (father[i]==-1)counts++;
        }
        cout<<counts-1<<endl;
    }
    return 0;
}