题解 | #畅通工程#

并查集问题

#include <iostream>
#include <vector>
using namespace std;

void Initial(vector<int>& s) {
    for(int i = 1; i < s.size(); i++) {
        s[i] = -1;
    }
}

int Find(vector<int>& s, int x) {
    int root = x;
    while (s[root] >= 0) {
        root = s[root];
    }
    while (x != root) {
        int t = s[x];
        s[x] = root;
        x = t;
    }
    return root;
}

void Union(vector<int>& s, int a, int b) {
    int roota = Find(s, a);
    int rootb = Find(s, b);
    if (roota == rootb) return;
    if (s[roota] <= s[rootb]) {
        s[roota] += s[rootb];
        s[rootb] = roota;
    }
    else {
        s[rootb] += s[roota];
        s[roota] = rootb;
    }
}

int main()
{
    int n, m;
    while (scanf("%d", &n) != EOF) {
        if (n == 0) break;
        scanf("%d", &m);
        vector<int> s(n+1, 0);
        Initial(s);
        while (m--) {
            int a, b;
            scanf("%d %d", &a, &b);
            Union(s, a, b);
        }
        int result = 0;
        for (int i = 1; i < s.size(); i++) {
            if (s[i] < 0) {
                result++;
            }
        }
        result--;
        printf("%d\n", result);
    }
    return 0;
}