题解 | 第一题

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

struct Node {
    int father, height;
    //Node(int f, int h): father(f), height(h) {}
};

map<int, Node> father_height;


void Initial(int x) {
    map<int, Node>::iterator it = father_height.find(x);
    if (it == father_height.end()) {
        Node node;
        node.father=x;
        node.height=0;
        father_height[x]=node;
    }
}

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

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

int main() {
    int x, y;
    while (cin >> x >> y) {
        Initial(x);
        Initial(y);
        Union(x, y);
    }

    int answer = 0;
    map<int,Node>::iterator it=father_height.begin();
    for (; it!=father_height.end(); it++) {
        if (it->second.father==it->first) {
            answer++;
        }
    }
    cout << answer << endl;
    return 0;

}