题解 | #畅通工程#

思路：并查集合并城镇，之后用set判断连通块数量

注意输入格式 while(cin>>n)输入，不然会不通过

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<unordered_set>
using namespace std;

const int N = 1010;
int p[N];

void init() {
    for (int i = 0; i < N; i++) p[i] = i;
}

int find(int u) {
    if (p[u] != u) p[u] = find(p[u]);
    return p[u];
}

void un(int u, int v) {
    int root1 = find(u), root2 = find(v);
    if (root1 != root2) {
        p[root1] = root2;
    }
}

int main() {

    int n, m;

    while (cin >> n) {
        init();
        if (n == 0) break;
        cin >> m;
        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;
            if (find(a) != find(b)) un(a, b);
        }

        unordered_set<int> st;
        for (int i = 1; i <= n; i++) {
            st.insert(find(i));
        }

        cout << st.size() - 1 << endl;
    }

    return 0;
}