poj 1733_Parity game_并查集

发布于 2019-04-29 853 次阅读

题目大意

每次给出一个01序列中一段数1的奇偶性，求不冲突的最大数

思路

就是一个并查集然后用map离散一下，将全部的数存起来就可以了

#include 
#include 
#include 
#include 
using namespace std;
#define max 100000
int f[max+1],n,m,a[max+1];
map  p;
int find(int x)
{
    if (f[x]==-1) return x;
    int xx=f[x];
    f[x]=find(f[x]);
    a[x]=(a[x]+a[xx])%2;
    return f[x];
}
int insert(int x,int y,int odd)
{
    int xx=find(x),yy=find(y);
    if (xx!=yy)
    {
        f[xx]=yy;
        a[xx]=(a[x]+a[y]+odd)%2;
        return true;
    }
    else 
    {
        if ((a[x]+a[y])%2==odd)
            return true;
        else return false;
    }
}
int main()
{
    scanf("%d%d",&m,&n);
    for (int i=0;i<=max;i++)
        f[i]=-1;

    int k=1,i;
    for (i=0;i>x>>y>>s;
        x--;
        if (p.find(x)==p.end())
        {
            p[x]=k++;
        }
        if (p.find(y)==p.end())
        {
            p[y]=k++;
        }
        int odd;
        if (s=="odd") odd=1;
        else odd=0;
        if (!insert(p[x],p[y],odd)) break;
    }
    printf("%d\n",i);

}

]]>