题解 | #第一题#

#include <iostream>

using namespace std;

int father[1000010];
int height[1000010];
bool visit[1000010];

void Init() {
    for (int i = 0; i < 1000010; i++) {
        father[i] = i;
        height[i] = 0;
        visit[i] = false;
    }
}

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

void Union(int x, int y) {
    x = Find(x);
    y = Find(y);
    if (x != y) {
        if (height[x] < height[y]) {
            father[x] = y;
        } else if (height[x] > height[y]) {
            father[y] = x;
        } else {
            father[y] = x;
            height[x]++;
        }
    }

}

int main() {
    Init();
    int x, y;
    int MaxNum = 0;
    while (scanf("%d%d", &x, &y) != EOF) {
        Union(x, y);
        visit[x] = true;
        visit[y] = true;
        MaxNum = MaxNum > x ? MaxNum : x;//为了缩小下面的遍历范围 保留这一个文件中最大编号的节点
        MaxNum = MaxNum > y ? MaxNum : y;
    }
    int component = 0;
    for (int i = 1; i <= MaxNum; i++) {
        if (!visit[i])
            continue;
        if (father[i] == i)
            component++;
    }
    printf("%d\n",component);
    return 0;
}