题解 | #畅通工程#

• 求连通分量个数——并查集

#include<iostream>
using namespace std;
const int maxn=1010;
int city[maxn];
int height[maxn];

void Initial(int n){
    for(int i=1;i<=n;i++){
        city[i]=i;
        height[i]=1;
    }
    return ;
}
int Find(int x){//路径压缩查找
    if(x!=city[x]){
        city[x]=Find(city[x]);
    }
    return city[x];
}

void Union(int x,int y){//低树合并到高树
    x=Find(x);
    y=Find(y);
    if(height[x]>height[y]){
        city[y]=x;
        height[y]=height[x];
    }
    else if(height[x]<height[y]){
        city[x]=y;
        height[x]=height[y];
    }
    else {
        city[x]=y;
        height[y]++;
        height[x]=height[y];
    }
    return;
}
 int main(){
     int  n,m;
     while(scanf("%d",&n)!=EOF){
         if(n==0)break;
         scanf("%d",&m);
         Initial(n);
         int x,y;
         for(int i=0;i<m;i++){
             scanf("%d%d",&x,&y);
             Union(x,y);
         }
         int ans=-1;
         for(int i=1;i<=n;i++){
             if(Find(i)==i)ans++;//查找连通分量
         }
         printf("%d\n",ans);
     }
     return 0;
 }