题解 | #畅通工程#

#include <iostream>

using namespace std;
#define N 1000

int father[N];//每个元素父亲下标
int height[N];

void Init(int n) {
    //最开始每一个元素单独构建一个集合
    for (int i = 1; i <= n; i++) {
        father[i] = i;//每个元素都是自己的根
        height[i] = 1;
    }
}

int find(int x) {
    if (x != father[x]) {
        //他还有父亲
        //优化，压缩路径，找到祖先后先不返回，而是设置为自己的新父亲
        father[x] = find(father[x]);
    }
    //x是树的根
    return father[x];
}

void Union(int x, int y, int &num) {
    //合并两棵树,也可以路径压缩,大树吞并小树
    int X = find(x);
    int Y = find(y);
    if (X != Y) {
        num--;
    }
    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 (scanf("%d %d", &n, &m) != EOF) {
        if (n == 0 && m == 0) {
            break;
        }
        Init(n);
        int num = n;
        for (int i = 0; i < m; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            Union(x, y, num);
        }
        cout << num-1 << endl;

    }
    return 0;
}