题解 | #畅通工程#

//n个联通分量只需要n-1条边即可联通，所以本题只需要求出有多少个联通分量
//用并查集合并出各个联通分量
#include <iostream>
#include<cstring>
using namespace std;
const int maxn = 1000 + 10;
int  father[maxn];
int height[maxn];//每个节点的高度，用于高树合并矮树
void init(int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i;
        height[i] = 0;
    }
}

int find(int x) {
    if (x != father[x]) {
        //return find(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] += 1; //并查集中唯一可以让高度增加的方法
        }

    }
}

int main() {
    int n, m;
    while (cin >> n) {
        if (n == 0) {
            break;
        }
        cin >> m;
        int x, y;
        init(n + 1);
        while (m--) {

            cin >> x >> y;
            Union(x, y);
        }
        int component = 0;
        for (int i = 1; i <= n; i++) {
            if (i == find(i)) {
                component += 1;
            }
        }
        cout << component - 1 << endl;
    }
}
// 64 位输出请用 printf("%lld")