POJ1733 Parity game

这题的大意是对于一个正整数的区间，有若干句话，判断第一句错误的位置，每句话所描述的意思是对于一个区间[a, b]有奇数个1或是偶数个1。[a,b]有1的个数的奇偶性可以通过判断[0,a-1]到[0,b]的奇偶性异同来判断。相同的话，用0表示，不同的话，用1表示。则这种关系是满足传递性的。对于上述转换过来的问题，与原问题是等价的。然后用并查集来维护这之间的关系就可以了。

感谢：

http://hi.baidu.com/yhc0/blog/item/faede08f7095e3f2503d9215.html
http://hi.baidu.com/lilymona/blog/item/16ac11970ebba1037af4801c.html

http://blog.sina.com.cn/s/blog_3f3a72e30100devr.html

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <math.h>
using namespace std;

const int MAX =  50005;

struct NODE
{
    int f, w;
    NODE() 
    {
        f = -1;
        w = 0;
    }
}node[MAX];

int a[MAX], b[MAX], c[MAX];

map<int, int> mm;
vector<int> v;

void ready()
{
    for(int i = 0; i < MAX; i++)
        node[i] = NODE();
    mm.clear();
}

void hash(vector<int> v)
{
    int cnt = 0;
    sort(v.begin(), v.end());
    mm[v[0]] = cnt++;
    for(int i = 1; i < v.size(); i++)
    {
        if(v[i] != v[i - 1])  mm[v[i]] = cnt++;
    }
}

int myFind(int x)
{
    if(node[x].f == -1)  return x;
    int f = myFind(node[x].f);
    node[x].w += node[node[x].f].w;
    node[x].w %= 2;
    node[x].f = f;
    return f;
}

void join(int x, int y, int z)
{
    int xx = myFind(x);
    int yy = myFind(y);
    node[yy].f = xx;
    node[yy].w = (z + node[x].w - node[y].w + 2) % 2;
}

int main()
{
    int K;
    //while(scanf("%d%d", &K, &K) != EOF)
    {
        scanf("%*d%d", &K);
        //vector<int> v;
        v.clear();
        ready();
        for(int i = 0; i < K; i++)
        {
            string t;
            scanf("%d%d", &a[i], &b[i]);
            a[i]--;
            v.push_back(a[i]);
            v.push_back(b[i]);
            cin >> t;
            if(t == "even")  c[i] = 0;
            else  c[i] = 1;
        }
        if(K)  hash(v);
        int j = 0;
        for(j = 0; j < K; j++)
        {
            a[j] = mm[a[j]];
            b[j] = mm[b[j]];
            int aa = myFind(a[j]);
            int bb = myFind(b[j]);
            if(aa != bb)
            {
                join(a[j], b[j], c[j]);
            }
            else
            {
                if((node[a[j]].w - node[b[j]].w + 2) % 2 != c[j])
                    break;
            }
        }
        printf("%d\n", j);
    }
}