题解 | #畅通工程#

#include <iostream>
using namespace std;

int father[1000];
int height[1000];

void Initial(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[x]>height[y])father[y]=x;
        else
        {
            father[y]=x;
            height[x]++;
        }
    }
}

int main() {
    int n,m;
    while (cin >>n>>m) { 
        if(n==0)break;

        Initial(n);//给n个城镇都分别创建一棵树

        for(int i=1;i<=m;i++)
        {
            int x,y;cin>>x>>y;
            Union(x,y);//合并集合
        }

        int answer=-1;
        for(int i=1;i<=n;i++)
        {
            if(Find(i)==i)//每个集合的根节点都唯一，当前点就是根节点的话，说明找到了一个新集合
            answer++;
        }
        cout<<answer<<endl;
    }
}