题解 | #第一题#

#include <iostream>
#include "map"

#define  N 65535;
using namespace std;
map<int, int> son_TO_Father;
//连通问题直接想到并查集

//找爸爸
int FindFather(int u) {
    if (u == son_TO_Father[u]) {
        return u;
    } else {
        son_TO_Father[u] = FindFather(son_TO_Father[u]);
        return son_TO_Father[u];
    }
}

//合并两个集合
void UnionSet(int u, int v) {
    int u_root = FindFather(u);
    int v_root = FindFather(v);
    if (u_root != v_root) {
        son_TO_Father[v_root] = u_root;
    }
}

//判断连通子图的个数
int CountGraph() {
    int count = 0;
    for (auto it : son_TO_Father) {
        if (it.first == it.second) {
            ++count;
        }
    }
    return count;
}

int main() {
    int a, b;
    while (cin >> a >> b && a && b) {//注意while处理多个case
	  //初始化并查集
        if (son_TO_Father.find(a) == son_TO_Father.end()) {
            son_TO_Father[a] = a;
        }
        if (son_TO_Father.find(b) == son_TO_Father.end()) {
            son_TO_Father[b] = b;
        }
        UnionSet(a, b);
    }
    printf("%d\n", CountGraph());
    return 0;
}