题解 | 第一题

这题解法大家看个乐子就好，并查集咱也不搞路径压缩了，随便并，只要并到一起就行，结点个数不知道那就初始化一个超大的节点数量，能ac就行

#include <cstdio>
using namespace std;
#define N 1000001

int father[N];
int hash[N]; // 标识出现过的结点编号

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

int Find(int x) {
    if (x != father[x]) {
        return Find(father[x]);
    }
    return father[x];
}

void Union(int m, int n) {
    int x = Find(m);
    int y = Find(n);
    father[x] = y; // 把x并到y下面
}

int main() {
    int m, n;
    init(N);
    while (scanf("%d%d", &m, &n) != EOF) {
        Union(m, n);
        hash[m]++;
        hash[n]++;
    }
    int ans = 0;
    // 若有结点它的根是自己，说明是一个集合的根
    for (int i = 0; i < N; i++) {
        if (hash[i] && father[i] == i) {
            ans++;
        }
    }
    printf("%d\n", ans);
    return 0;
}