题解 | #畅通工程#

//并查集或者BFS，DFS求有几个连通分量
#include<iostream>
#include<set>
using namespace std;

int father[1200];

int findFather(int x) {
    if (x == father[x]) {
        return x;
    } else {
        father[x] = findFather(father[x]);
        return father[x];
    }
}

void mergeUnion(int x, int y) {
    int x_father = findFather(x);
    int y_father = findFather(y);
    father[y_father] = father[x];
}
int main() {
    int N, M;
    while (scanf("%d", &N) != EOF) {
        if (N == 0) {
            break;
        }
        for (int i = 0; i < 1200; i++) {
            father[i] = i;
        }
        scanf("%d", &M);
        while (M--) {
            int a, b;
            scanf("%d %d", &a, &b);
            mergeUnion(a, b);
        }
        set<int>blocks;
        for (int i = 1; i <= N; i++) {
            blocks.insert(findFather(i));
        }
        printf("%d\n", blocks.size() - 1);
    }
}