题解 | #第一题#

//本题注意两件事，一是测试案例数据量很大，设置的数组大小记得扩大
//二是输入的节点编号不是连续的，为了方便出路将节点编号转变成连续的然后再用并查集的思想即可
#include <iostream>
#include<cstring>
#include<map>
using namespace std;
const int maxn = 1e6+ + 10;
int  father[maxn];
int height[maxn];//每个节点的高度，用于高树合并矮树
void init(int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i;
        height[i] = 0;
    }
}

int find(int x) {
    if (x != father[x]) {
        //return find(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] += 1; //并查集中唯一可以让高度增加的方法
        }

    }
}

int main() {
    int x, y;
    init(maxn);
    map<int, int> m;
    int num = 0;
    while (scanf("%d %d", &x, &y) != EOF) {
        if (m[x] == 0) {
            m[x] = num++;
        }
        if (m[y] == 0) {
            m[y] = num++;
        }

        Union(m[x], m[y]);
    }
    int component = 0;
    for (int i = 0; i < num; i++) {
        if (i == find(i)) {
            component += 1;
        }
    }
    cout << component  << endl;
}