1182食物链

  用并查集，方法模仿POJ2492A Bug's Life， 这题是2*n个数，如果a和b是异性，那么a和b+n，b和a+n是同性，这样在判断a和b是否是同性时可以通过a+n，或b+n来判断。
  而1182 这题是类似的方法，如果 b 被 a 吃，那么 a 和 b+n ， a+n 和 b+2*n ，b 和 a+2*n
是同类。如果输入有“1 A B”， 如果A,B不同类 或  B 吃 A 则这句话是假的。



#include<cstdio>
int pre[150002];
void init(int n)
{
int i;
for(i=0;i<=n*3;i++)
{
pre[i]=-1;
}
}
int find(int x)
{
int p;
p=x;
while(pre[p]>=0)
{
p=pre[p];
}
return p;
}
int unit(int x,int y)
{
    int a,b;
    a=find(x);b=find(y);
    if(a==b)
return 0;
    else
    if(pre[a]<pre[b])
    {
        pre[a]+=pre[b];pre[b]=a;
    }
    else
    {
        pre[b]+=pre[a];pre[a]=b;
    }
    return 0;
}
int main()
{
int n,k,i,j,a,b,c;
scanf("%d%d",&n,&k);
init(n);
int ans = 0;
while(k--)
{
    scanf("%d%d%d",&a,&b,&c);
    if(b>n||c>n||(a==2&&b==c))
           {
            ans ++;
            continue;
           }
        if(a==1)
        {
            if(!(((find(b)==find(c+n))||(find(b+n)==find(c+2*n))||(find(c)==find(b+2*n)))
               ||((find(c)==find(b+n))||(find(c+n)==find(b+2*n))||(find(b)==find(c+2*n))))) // 如果不是 A 吃 B 或  B 吃 A
            {
                unit(b,c);
                unit(b+n,c+n);
                unit(b+2*n,c+2*n);
            }
            else ans++;
        }
        if(a==2)
        {
            if(find(b)==find(c)||((find(c)==find(b+n))||(find(c+n)==find(b+2*n))||(find(b)==find(c+2*n))))// 如果A,B不同类 或  B 吃 A
            ans ++;
            else
            {
                unit(b,c+n);
                unit(b+n,c+2*n);
                unit(c,b+2*n);
            }
        }
}
printf("%d\n",ans);
}