题解 | #第一题#

#include <iostream>
#include <sys/types.h>
using namespace std;

const int MAXN = 1000000 + 10;
int father[MAXN];
int height[MAXN];
int visit[MAXN];
void Initial(int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i;
        height[i] = 0;
        visit[i] = 0;
    }
}
int Find(int n) {
    if (n != father[n]) {
        father[n] = Find(father[n]);
    }
    return father[n];
}
void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a != b) {
        if (height[a] < height[b]) {
            father[a] = b;
        } else if (height[a] > height[b]) {
            father[b] = a;
        } else {
            father[b] = a;
            height[a]++;
        }
    }
}
int main() {
    int n, m;
    Initial(MAXN);
    while (cin >> n >> m) {
        visit[n]++;
        visit[m]++;
        Union(n, m);
    }
    
    int ans = 0;
    for (int i = 1; i < MAXN; i++) {
        if (visit[i]!=0 && Find(i) == i) {
            ans++;
        }
    }
    cout << ans << endl;
}
// 64 位输出请用 printf("%lld")