D. Mahmoud and a Dictionary 種類并查集

​​http://codeforces.com/contest/766/problem/D​​

所謂種類并查集，題型一般如下：給定一些基本資訊給你，然後又給出一些資訊，要求你判斷是真是假。例如給出a和b支援不同的隊伍，而且b和c也是支援不同的隊伍，由于隊伍隻有兩支（就是說隻有兩種），是以可以推出a和c是支援同一個隊伍。

你可能會想用兩個并查集，一個并查集存放一個隊伍。但是這樣是不行的，十分麻煩。因為你想想，如果給出[a,b]不同，然後[c,d]不同，如果我按照左邊的放在同一個集合，那麼我接着[a,c]不同，這樣就會是(a,d)相同，這樣的話，你要更改那個并查集，是十分麻煩的。

正解：隻用一個并查集，而且再維護一個數組rank[i]表示i與father的關系，0表示支援同一個球隊，1表示不同，這樣的話，就可以根據rank[x]==rank[y]來判斷是不是支援相同的了。爸爸支援誰沒所謂啊，我們不關心支援哪個球隊，我們隻關心支援的是否一樣罷了。rank[]數組壓縮路徑和并查集一樣的，隻不過其中要列些資料，推些公式出來。

大緻思路和食物鍊那些題目差不多。

設rex[i]表示i号頂點和爸爸的關系是什麼

0，表示同一類型，1表示不同類型。

然後細心推個公式，就行了

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
const int maxn = 1e5 + 20;
int fa[maxn], rex[maxn];
map<string, int>mp;
int tofind(int u) {
    if (fa[u] == u) {
        rex[u] = 0;
        return u;
    }
    int t = fa[u];
    fa[u] = tofind(fa[u]);
    rex[u] = (rex[u] + rex[t]) % 2;
    return fa[u];
}
int tomerge(int x, int y, int val, int is) {
    int tx = x, ty = y;
    x = tofind(x);
    y = tofind(y);
    if (is) {
        if (x != y) return 3;
        if (rex[tx] != rex[ty]) {
            return 2;
        } else return 1;
    }
    if (x != y) {
        fa[y] = x;
        rex[x] = 0;
        rex[y] = (rex[ty] + rex[tx] + val) % 2;
        return 1;
    }
    return !((rex[tx] + rex[ty] + val) % 2);
}
void work() {
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= n; ++i) {
        string s;
        cin >> s;
        mp[s] = i;
        fa[i] = i;
    }
    for (int i = 1; i <= m; ++i) {
        int id;
        string s1, s2;
        cin >> id >> s1 >> s2;
        id--;
        if (tomerge(mp[s1], mp[s2], id, 0)) {
            cout << "YES" << endl;
        } else cout << "NO" << endl;
    }
    for (int i = 1; i <= q; ++i) {
        string s1, s2;
        cin >> s1 >> s2;
        cout << tomerge(mp[s1], mp[s2], 0, 1) << endl;
    }
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    IOS;
    work();
    return 0;
}