Parity game POJ - 1733（种类并查集+离散化）

复习了一下，种类并查集的权值更新方法。对离散化的操作更深入的了解。
注意离散化的各函数的返回值。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e4+100;
int pre[N],value[N];
int pos[N],first[5005],last[5005];
char ss[5005][6];
int Find(int x)
{
    if(pre[x]!=x)
    {
        int t=pre[x];
        pre[x]=Find(pre[x]);
        value[x]=(value[t]+value[x]+2)%2;
    }
    return pre[x];
}
void Union(int x,int y,int z)
{
    int px=Find(x),py=Find(y);
    if(px!=py)
    {
        pre[py]=px;
        value[py]=(value[x]-value[y]+z+2)%2;
    }
}
int main()
{
    int n,m;
    while(scanf("%d",&n)!=EOF)
    {
        scanf("%d",&m);
        for(int i=0;i<N;i++)
        {
            pre[i]=i;
            value[i]=0;
        }
        memset(ss,0,sizeof(ss));
        int cnt=0,num=-1,ans=0;
        bool f=0;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&first[i],&last[i]);
            scanf("%s",ss[i]);
            pos[++cnt]=first[i];
            pos[++cnt]=last[i];
        }//离散化：
        sort(pos+1,pos+cnt+1);//排序
        int tn=unique(pos+1,pos+cnt+1)-pos-1;//去重
        for(int i=1;i<=m;i++)
        {//二分查找
            int tx=lower_bound(pos+1,pos+tn+1,first[i])-pos;//cout<<"tx="<<tx<<endl;
            int ty=lower_bound(pos+1,pos+tn+1,last[i])-pos;//cout<<"ty="<<ty<<endl;
            if(strcmp(ss[i],"even")==0)
                num=0;
            else
                num=1;
            int px=Find(tx-1);
            int py=Find(ty);
            if(px==py)
            {
                if((value[ty]-value[tx-1]+2)%2==num)//WA:tx写成了ty
                    ans++;
                else
                    break;
            }
            else
            {
                ans++;
                Union(tx-1,ty,num);
            }
            //cout<<"value[ty]="<<value[ty]<<endl;
        }
        printf("%d\n",ans);
    }
    return 0;
}