是一道挺不错的并查集题目。不同于普通并查集的题，这道题不仅仅需要对一种情况进行分集合，而是对三种情况区分集合：两种动物同类，A吃B，B吃A。这样我们可以把数组开大三倍，a[i]表示第i个动物属于第1类动物这种情况，a[i+n]表示第i个动物属于第2类动物这种情况,a[i+2*n]表示第I个动物属于第3类动物这种情况。
当输入查询时，如果判断是正确的，就把可能发生的几种情况都放进同一个集合里面。例如，加入x和y是同类动物这个查询没有错误，那就把a[x]和a[y]、a[x+n]和a[y+n]、a[x+2*n]和a[y+2*n]分别放进同一个集合里。判断不正确就从反面进行查找。
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<list>
#include<string>
#include<map>
using namespace std;
#define maxn 50050
int father[maxn*3];
int find(int n)
{
if(n!=father[n]) father[n]=find(father[n]);
return father[n];
}
int main()
{
int n,k;
int sum=0;
int kind,x,y;
scanf("%d%d",&n,&k);
for(int i=0;i<=3*n;i++)
{
father[i]=i;
}
while(k--)
{
scanf("%d%d%d",&kind,&x,&y);
if(x>n||x<=0||y>n||y<=0)
{
sum++;
continue;
}
if(kind==1)
{
if(find(x)==find(y+n)||find(x)==find(y+2*n))
sum++;
else
{
father[find(x)]=find(y);
father[find(x+n)]=find(y+n);
father[find(x+2*n)]=find(y+2*n);
}
}
else if(kind==2)
{
if(find(x)==find(y)||find(x)==find(y+2*n)||find(x+2*n)==find(y+n))
sum++;
else
{
father[find(x)]=find(y+n);
father[find(x+n)]=find(y+2*n);
father[find(x+2*n)]=find(y);
}
}
}
printf("%d\n",sum);
return 0;
}