题解 | 第一题

#include <iostream>
#include <map>

using std::cout;
using std::endl;
using std::map;

map<int, int> father;
map<int, int> height;

// 找到节点n的根节点,并把沿途节点的father节点全部设为root
// 即具有压缩路径的功能
int FindRoot(int n) {
    if (father[n] != n) { // 若当前节点不是本集合的根节点
        father[n] = FindRoot(father[n]);
        /* height[n]不用管,因为我们只关心根节点的高度(也就是本棵树/本集和的高度) */
    }
    return father[n];   // 本集和的根节点
}

void Union(int n1, int n2) {
    int root1 = FindRoot(n1);
    int root2 = FindRoot(n2);
    if (root1 == root2) // 两个节点本就在同一个集合中
        return; // 直接返回就行
    // 接下来说明两节点属于两个集合,就要涉及到集合合并操作(矮树合并到高树中)
    else if (height[root1] > height[root2]) {
        father[root2] = root1;
    } else if (height[root1] < height[root2]) {
        father[root1] = root2;
    } else { // 两棵树同样高
        father[root2] = root1;  // 将2树合并到1树中
        height[root1]++;    // 1树的高度必然+1
    }
}

int main() {
    int n1, n2;
    while (scanf("%d%d", &n1, &n2) != EOF) {
        if (father.count(n1) == 0) { // 该节点为新节点
            father[n1] = n1;    //  将该节点作为新的集合的根节点
            height[n1] = 1; // 新的集合的高度为1
        }
        if (father.count(n2) == 0) { // 同上
            father[n2] = n2;
            height[n2] = 1;
        }
        Union(n1, n2);  // 将两个节点所在的集合进行合并
    }

    // 计算连通分量的个数
    int cnt = 0;    // 记录联通分量的个数(father[n] == n)
    for (auto& elem : father) {
        if (elem.first == elem.second)
            ++cnt;
    }
    cout << cnt << endl;

    return 0;
}