题解 | 畅通工程

#include <bits/stdc++.h>
using namespace std;

const int MAXN=1000;

int father[MAXN];
int height[MAXN];

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

int Find(int x){
    if(x!=father[x]) father[x]=Find(father[x]);
    return father[x];
}

void Union(int x,int y){
    x=Find(x);
    y=Find(y);
    if(x!=y){
        if(height[x]<height[y])father[x]=y;
        else if(height[y]<height[x]) father[y]=x;
        else {
            father[y]=x;
            height[x]++;
        }
    }
}

int main(){
    int n,m;
    while(cin>>n>>m){
        if(n==0)break;
        init(n);//初始化所有的乡镇节点
        while(m--){
            int x,y;
            cin>>x>>y;
            Union(x,y);
        }
        int ans=-1;//孤立个数减一就是最后结果，所以这个赋值为-1
        for(int i=1;i<=n;i++){//乡镇1编号
            if(Find(i)==i)ans++;//说明孤立
        }
        cout<<ans<<endl;
    }
}

并查集是解决连通图问题的最好手段，首先要构建一个并查集，并查集的构建是基于并查集的默认状态开始的，默认所有点孤立，然后根据高度去并，并的方法就是把父节点直接给到另一个对象上，所以我们的并查集为双亲表示法的树，然后我们需要其高度完成判断，为了方便，我们直接映射一个平行的以序号为标记的高度数组作为高度存储，对于相同高度，我们的并会导致高度加一，给被认为是新的父节点的树，然后，我们根据初始化条件，可以发现，如果采用递归方式，可以发现如果父节点就是自己即孤立，所以根据这个，设计Find函数，然后Find函数成立，则孤立，对于孤立要多少条路，就是孤立数量-1，所以ans设为-1，即可得到结果