题解 | #第一题#

思路：

因为没有给定数据范围，所以用map作为并查集数组；每次输入两个节点啊a，b时，判断是否在map中出现过，如果第一次出现则要初始化：mp[a] = a；之后将a、b合并；

最后判断集合个数时遍历map，找到mp[x] = x即为一个集合

#include<iostream>
#include<unordered_map>
using namespace std;

unordered_map<int, int> mp;

int find(int x) {
    if (mp[x] != x) mp[x] = find(mp[x]);
    return mp[x];
}

//a子树合并到b上
void un(int a, int b) {
    int root1 = find(a), root2 = find(b);
    mp[root1] = root2;
}

int main() {

    int x, y;
    while (cin >> x) {
        cin >> y;
        //如果未出现过,加入集合
        if (mp.count(x) == 0) mp[x] = x;
        if (mp.count(y) == 0) mp[y] = y;

        int a = find(x);
        int b = find(y);
        if (a != b) un(a, b);
    }

    int sum = 0;
    for (auto x : mp) {
        if (x.first == x.second) sum++;
    }

    cout << sum << endl;

    return 0;
}