题意：有N只动物，分别编号1-N。所有动物都属于A、B、C中的其中一种。已知A吃B，B吃C，C吃A。按顺序给出K个信息
第一种：x和y是同一种类；第二种，x吃y。求问这些信息中有多少个假信息？
思路：我是看《挑战程序设计竞赛》的。没想到并查集也可以维护两种关系。
题目中，有捕猎关系和“同一种”关系。
可以通过给每个动物i创建3个元素x-A,x-B,x-C，分别进行维护。
如果x-A与y-B为同一组，那么就代表 动物x为A种类且动物y为B种类。
所以，对上面两种信息，可以分别进行下面的操作：
第一种，x和y为同一种类，那么我们就把x-A与y-A，x-B与y-B，x-C与y-C放入一组（这样就能保证，若x为A，那么y也为A，或者若x为B，y为B...）
第二种，x吃y，那么只有3情况：1，x为A且y为B；2，x为B且y为C；3，x为C且y为A；所以就把x-A,y-B....放入同一组
不过在进行前面操作时，要判断是否有冲突。
AC代码：
#include <cstdio>
using namespace std;
const int MAX_N = 50000;
int fa[3*MAX_N+1],n,x,y,t,k;
int find(int x)
{
if(fa[x] == x) return x;
else return fa[x] = find(fa[x]);
}
void unite(int x, int y)
{
x = find(x);
y = find(y);
if(x == y) return ;
fa[x] = y;
}
bool same(int x, int y)
{
return find(x) == find(y);
}
void init()
{
for(int i = 1; i <= n*3; i++)
fa[i] = i;
}
void solve()
{
int ans = 0;
while(k--)
{
scanf("%d %d %d", &t, &x, &y);
//编号超界
if(x < 1 || x > n || y < 1 || y > n)
{
ans++;
continue;
}
if(t == 1)
{
//判定x和y是不是同一种类
//如果x-A与y-B同一组说明，x为A种类且y为B种类，那么显然x和y不可能是同一种类，故该信息是假信息
//同理，如果x-A与y-C为同一组....
if(same(x,y+n) || same(x,y+2*n) ) ans++;
else
{
unite(x,y);
unite(x+n, y+n);
unite(x+2*n, y+2*n);
}
}else
{
//判定x能否吃y
//如果x等于y或者x为A，y为C，那么x不能吃y ，所以该信息为假信息
if(same(x,y) || same(x,y+2*n)) ans++;
else
{
unite(x,y+n);
unite(x+n,y+2*n);
unite(x+2*n, y);
}
}
}
printf("%d
", ans);
}
int main()
{
scanf("%d %d", &n, &k);
init();
solve();
return 0;
}