Ural_1003 Parity(并查集)

　　/*发现并查集的应用太巧妙了。。。大体思路：从题中可以看出来如果(i, j)是even
的话，sum(i-1) 和 sum(j)的奇偶性相同。（i， j）如果是odd的话则其奇偶行不同。定
义奇偶性为朋友，不同则为敌人。

这样按照奇偶性分成连个集合。
same[i] = {x|sum[x]与sum[i]同奇偶}（即i的朋友集）
diff[i] = {x|sum[x]与sum[i]不同奇偶}（即i的敌人集）

如果(i, j)是even，则分别合并（same(i-1), same(j)）和（dirr[i-1] , diff(j)）。如果是
odd，则因为不是奇就是偶，所以，一个的朋友和另一个的敌人合并（敌人的敌人就是
朋友，呵呵）

既合并( same(i-1), diff(j) ),  ( diff(i-1), same(j) )。如果出现读入的数据(i, j)的阵营与输入
的even,odd不相符的话则说明这句是假话。

ps：数据比较大(10^9)，离散化了一下。内存还可以吧，不高不底。^ ^

My Code:*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;

const int N = 5005;
const int block = 5005;

struct eq {
    int x;
    int y;
    char s[10];
} q[N];

int p[N*2], tmp[N*2];
int f[N*2], Rank[N*2];
int cnt, n;

void init() {
    for(int i = 0; i <= N+N; i++) {
        f[i] = i; Rank[i] = 0;
    }
}

int get_p(int x) {
    int l, r, mid;
    l = 0; r = cnt-1;
    while(l < r) {
        mid = (l + r) >> 1;
        if(p[mid] >= x)    r = mid;
        else    l = mid + 1;
    }
    return l;
}

int find(int x) {
    int k, r, j;
    r = x; k = x;
    while(r != f[r])    r = f[r];

    while(k != r) {
        j = f[k];
        f[k] = r;
        k = j;
    }
    return r;
}

void union_set(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y)    return ;
    if(Rank[x] > Rank[y])    f[y] = x;
    else {
        f[x] = y;
        if(Rank[x] == Rank[y])    ++Rank[y];
    }
}

int main() {
    //freopen("data.in", "r", stdin);

    int M, i, x, y;
    while(~scanf("%d", &M)) {
        if(M == -1)    break;

        scanf("%d", &n);


        for(i = 0; i < n; i++) {
            scanf("%d%d %s", &q[i].x, &q[i].y, q[i].s);
            q[i].x--;
            tmp[i*2] = q[i].x;
            tmp[i*2+1] = q[i].y;
        }
        init();
        sort(tmp, tmp+n+n);
        p[0] = tmp[0]; cnt = 1;

        for(i = 1; i < n+n; i++) {
            if(tmp[i] != tmp[i-1])    p[cnt++] = tmp[i];

        }

        for(i = 0; i < n; i++) {
            
            x = get_p(q[i].x);
            y = get_p(q[i].y);

            if(q[i].s[0] == 'e') {
                if(find(x) == find(y + block))     break;
                union_set(x, y);
                union_set(x + block, y + block);
            } else {
                if(find(x) == find(y))     break;
                union_set(x, y + block);
                union_set(x + block, y);
            }
        }
        printf("%d\n", i);
    }
    return 0;
}