【hihoCoder第十四周】无间道之并查集

就是基础的并查集。0代表合并操作，1代表查询操作。一开始以为会卡路径压缩，忐忑的交了一版裸并查集，结果AC了。数据还是很水的。

以后坚持做hiho，当额外的练习啦~

#include <bits/stdc++.h>
using namespace std;

map<string, int> Hash;
int Father[1000005];

int getFather (int x) {
    if (x != Father[x]) {
        return getFather (Father[x]);
    }
    return x;
}

void Union (int p, int q) {
    int x = getFather (p);
    int y = getFather (q);
    if (x != y) {
        Father[y] = x;
    }
}

int main () {
    ios :: sync_with_stdio(false);
    cin.tie(0);
    int n, a, cnt = 1;
    string x, y;
    cin >> n;
    for (int i = 0; i < 100005; ++ i) {
        Father[i] = i;
    }
    while (n --) {
        cin >> a >> x >> y;
        if (a == 0) {
            if (!Hash[x]) {
                Hash[x] = cnt ++;
            }
            if (!Hash[y]) {
                Hash[y] = cnt ++;
            }
            Union (Hash[x], Hash[y]);
        } else {
            if (!Hash[x]) {
                Hash[x] = cnt ++;
            }
            if (!Hash[y]) {
                Hash[y] = cnt ++;
            }
            if (getFather (Hash[x]) == getFather (Hash[y])) {
                cout << "yes" << endl;
            } else {
                cout << "no" << endl;
            }
        }
    }
    return 0;
}