题解 | 畅通工程 并查集

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
using namespace std;

// 全局变量
int father[1001];
int setCount = 0;  // 统计并查集(相互不连通)的数量

// 初始化
void InitDisjoinSet(int n) {
    for (int i = 1; i <= n; i++) {
        father[i] = i;
    }
}

// 找根结点
int FindDisjoinSet(int u) {
    if (u == father[u]) {
        return u;
    } else {
        // 压缩路径
        father[u] = FindDisjoinSet(father[u]);
        return father[u];
    }
}

// 合并并查集
void UnionDisjoinSet(int u, int v) {
    int uroot = FindDisjoinSet(u);
    int vroot = FindDisjoinSet(v);
    if (uroot != vroot) {  // u v在不同集合里，将要合并，大集合数量减一
        setCount--;
    }
    father[vroot] = uroot;  //  v 挂载载 u 上
}

int main() {
    int m, n;
    while (scanf("%d", &n) != EOF) {
        if (n == 0) {
            break;
        }
        scanf("%d", &m);
        InitDisjoinSet(n);  // 初始化1-n个结点
        setCount = n;  // 刚开始，所有集合都独立

        for (int i = 0; i < m; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            UnionDisjoinSet(u, v);
        }
        printf("%d\n", setCount - 1);
    }
    return 0;
}