pku1733 Parity game(離散化+并查集)

這道題坑了我一下午 一直RE RE RE

把能改的都改了 結果是數組開小了

這道題就是哈希+并查集 哈希時要注意排序 去重

上代碼：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<map>
using namespace std;
#define MAX 14000
int   pa[MAX];
int    r[MAX];
int temp[MAX];
map<int,int>M;

struct data
{
    int l,r,is;
    data(){l=r=is=0;}
}num[MAX];

void init(int n)
{
    for(int i=0;i<10020;i++)
        pa[i]=i,r[i]=0;
}
int Find(int n)
{
    int pn=pa[n];
    if(n!=pa[n])
    {
        pa[n]=Find(pa[n]);
        r[n]=(r[n]+r[pn])%2;
    }
    return pa[n];
}

int Union(int x,int y,int rel)
{
    int px=Find(x);
    int py=Find(y);
    if(px==py)
    {
        if((r[x]+r[y])%2==rel)
            return 1;
        else return 0;
    }
    else
    {
        pa[py]=px;
        r[py]=(r[x]+r[y]+rel)%2;
        return 1;
    }
}

int main()
{
    int n,m,x,y,cut,k,jd;
    char s[10];
    while(scanf("%d",&n)!=EOF)
    {
        k=1;jd=cut=0;
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&num[i].l,&num[i].r);
            num[i].r++;
            scanf("%s",s);
            if(s[0]=='o')
                num[i].is=1;
            temp[k++]=num[i].l;
            temp[k++]=num[i].r;
        }
        sort(temp+1,temp+k);
        int p=unique(temp+1,temp+k)-(temp+1);
        for(int i=1;i<=p;i++)
            M[temp[i]]=i;
        init(p);
        for(int i=1;i<=m;i++)
        {
            x=M[num[i].l];
            y=M[num[i].r];
            if(Union(x,y,num[i].is)==0)
                break;
            cut++;
        }
        printf("%d\n",cut);
    }
    return 0;
}