题解 | 第一题

#include <iostream>
using namespace std;

#define MAXSIZE 640000
int T[MAXSIZE];
bool Avail[MAXSIZE];

void Init()
{
    for (int i = 0; i < MAXSIZE; i++) {
        T[i] = -1;
        Avail[i] = false;
    }
}

int FindRoot(int x) {
    while (T[x] >= 0) {
        x = T[x];
    }
    return x;
}

void Union(int a, int b)
{
    int rta = FindRoot(a);
    int rtb = FindRoot(b);
    if (rta == rtb)
        return;
    if (T[rta] < T[rtb]) {
        T[rta] += T[rtb];
        T[rtb] = rta;
    }
    else {
        T[rtb] += T[rta];
        T[rta] = rtb;
    }
}

int main() {
    Init();
    int a, b;
    while (cin >> a >> b) { // 注意 while 处理多个 case
        Avail[a] = true;
        Avail[b] = true;
        Union(a, b);
    }
    int cnt = 0;
    for (int i = 0; i < MAXSIZE; i++) {
        if (Avail[i] && T[i] < 0) {
            cnt++;
        }
    }
    cout << cnt;
    return 0;
}
// 64 位输出请用 printf("%lld")

题目是很基础的并查集。

坑点有两个，一个是数组不能开太小，还有一个是习惯了力扣模式返回值设成了结果，提交就报错，返回值要设置为零。