题解 | 畅通工程

#include <stdio.h>
#include <set>
using namespace std;

int FindDjsjointSet(int father[], int n) {
    if (father[n] == n) {
        return n;
    }
    father[n] = FindDjsjointSet(father, father[n]);
    return father[n];
}

void UnionDjsjointSet(int father[], int u, int v) {
    int uroot = FindDjsjointSet(father, u);
    int vroot = FindDjsjointSet(father, v);
    if (uroot != vroot) {
        father[vroot] = uroot;
    }
}

int main() {
    int m, n;
    while (scanf("%d %d", &m, &n) != EOF && m != 0) {
        int father[10005];
        for (int i = 1; i <= m; i++) {
            father[i] = i;
        }

        for (int i = 0; i < n; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            UnionDjsjointSet(father, u, v);
        }

        set<int> rootn;
        for (int i = 1; i <= m; i++) {
            rootn.insert(FindDjsjointSet(father, i));
        }

        printf("%d\n", (int)rootn.size() - 1);
    }

    return 0;
}