题解 | #第一题#

并查集

#include <iostream>
#include <vector>
using namespace std;
const int MAXN=1000010;

vector<int> s(MAXN, -1);
vector<bool> visited(MAXN, false);

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 a, b;
    while (cin >> a >> b) {
        Union(s, a, b);
        visited[a] = true;
        visited[b] = true;
    }
    int component = 0;
    for (int i = 0; i < MAXN; i++) {
        if (!visited[i]) continue;
        if (s[i] <= 0) component++;
    }
    cout << component << endl;
    return 0;
}