poj 1733(帶權並查集)

poj 1733(帶權並查集)

題意：有n個結點，給出了q個操作，操作是a b string表示結點a到結點b的和是奇數或偶數，輸出x(前x個操作都是正確的)。
題解：帶權並查集經典題，因為結點可能有10,000,000,000個，所以需要離散化，不用的點就不考慮了。因為要a加到b，如果a==b無法找到各自的根節點並判斷是否要合並，所以其實是mp[a - 1]到mp[b]並入集合。另外需要注意結點是有順序的，父親結點要大於等於子節點，這樣判斷才不會出錯，所以合並時要考慮兩個根結點的大小有不同關系式。

#include 
#include
using namespace std;
const int N = 10005;
int pa[N], n, q, cnt, rel[N], l[N], r[N];
char str[N][10];
map mp;

int get_parent(int x) {
    if (pa[x] != x) {
        int px = get_parent(pa[x]);
        rel[x] = (rel[x] + rel[pa[x]]) % 2;
        pa[x] = px;
    }
    return pa[x];
}

int main() {
    while (scanf("%d", &n) == 1) {
        scanf("%d", &q);
        mp.clear();
        cnt = 1;
        for (int i = 1; i <= q; i++) {
            scanf("%d%d%s", &l[i], &r[i], str[i]);
            if (!mp[l[i] - 1])
                mp[l[i] - 1] = cnt++;
            if (!mp[r[i]])
                mp[r[i]] = cnt++;
        }
        for (int i = 0; i <= cnt; i++) {
            pa[i] = i;
            rel[i] = 0;
        }
        int res = -1;
        for (int i = 1; i <= q; i++) {
            int flag = str[i][0] == 'e' ? 0 : 1;
            int px = get_parent(mp[l[i] - 1]);
            int py = get_parent(mp[r[i]]);
            if (px != py) {
                if (px < py) {
                    pa[px] = py;
                    rel[px] = (flag + rel[mp[r[i]]] - rel[mp[l[i] - 1]] + 2) % 2;
                }
                else {
                    pa[py] = px;
                    rel[py] = (rel[mp[l[i] - 1]] - flag - rel[mp[r[i]]] + 4) % 2;
                }
            }
            else {
                if ((rel[mp[l[i] - 1]] - rel[mp[r[i]]] + 2) % 2 != flag) {
                    res = i - 1;
                    break;
                }
            }
        }
        if (res == -1)
            res = q;
        printf("%d\n", res);
    }
    return 0;
}