此题按照《挑战程序设计竞赛（第2版）》P89的解法，不容易想到，但想清楚了代码还是比较直观的。
并查集模板（包含了记录高度的rank数组和查询时状态压缩）
const int MAX_N=*;
int par[MAX_N];
int rank[MAX_N];
//初始化，根为自身，高度为0
void init(int scab)
{
for(int i=;i<=scab;i++)
{
par[i]=i;
rank[i]=;
}
}
//查找，途径的所有结点都直接连到根上
int find(int x)
{
if(par[x]==x) return x;
return par[x]=find(par[x]);
}
//合并，把短链连接到长链上，保持结点高度的相对关系
int unite(int x,int y)
{
x=find(x);
y=find(y);
if(x==y) return ;
if(rank[x]<rank[y]) {par[x]=y; return ;}
par[y]=x;
if(rank[x]==rank[y]) rank[x]++;
return ;
}
并查集实现
并查集是用于维护“属于同一集合”的数据结构，然而这道题的“属于同一集合”并不指“是同类”，而是指“这几个情况若发生必然同时发生”。
我们从理解题意开始：
有N只动物，分别编号为1,2,...,N。所有动物属于A,B,C类中的一种，类之间有天然的A吃B,B吃C,C吃A的关系。
按如下两种格式顺序给出共K条信息（只表达了相对关系）:
1 x y: x,y是同类
2 x y: x吃y
每条信息若不符合常理（编号大于N，或自己吃自己）或与已有信息矛盾，则为错误。
问这K条信息有几条错误？
由于A,B,C之间的吃与被吃关系构成一个循环，所以三类的等级关系根本上也是相对的，那么每条信息都可以翻译成三种可能的实际情况。同时维护这三种可能
，就需要为每个动物x分配三个数组元素，分别表示x是A,x是B,x是C这三个事件。
同属一个集合的事件意味着“若发生必然同时发生”。
并查集需要用一个数组存储每个元素“属于哪一集合”，那么可以开一个长度为N*3的数组，用x,x+N,x+N*2分别表示x是A,x是B,x是C。
表示x与y是同类，需要维护这三种可能
unite(x,y); //x,y都是A
unite(x+n,y+n); //x,y都是B
unite(x+2*n,y+2*n); //x,y都是C
表示x吃y，需要维护这三种可能
unite(x,y+n); //x是A,y是B
unite(x+n,y+2*n); //x是B,y是C
unite(x+2*n,y); //x是C,y是A
想清楚了道理，代码就比较好理解了。注意由于从始至终只知道相对关系，同时维护了三种可能，所以判断矛盾的时候任选一种判断就可以了。
int main()
{
freopen("e.txt","r",stdin);
scanf("%d%d",&n,&k);
ans=;
init(n*);
while(k--)
{
scanf("%d%d%d",&d,&x,&y);
if(x>n||y>n)
{
ans++;
continue;
}
if(d==)
{//若想成为同类，就不可能有x吃y或y吃x的关系
if(find(x)==find(y+n)||find(y)==find(x+n))
ans++;
else
{
unite(x,y);
unite(x+n,y+n);
unite(x+*n,y+*n);
}
}
else if(d==)
{
if(x==y) ans++;
//若想x吃y，则x,y不可能是同类，也不可能y吃x
else if(find(x)==find(y)||find(y)==find(x+n))
ans++;
else
{
unite(x,y+n);
unite(x+n,y+*n);
unite(x+*n,y);
}
}
}
printf("%d\n",ans);
return ;
}
OJ运行结果如下：
这道题使我对并查集有了新的认识，想清楚“同属一个集合”代表什么很重要，不一定就是题目限定的“属于同一种”。
分析问题的难度有时会大于编程的难度，如果说代码能力可以通过刷题习得，那么分析问题的能力真的需要足够的知识储备和一些“创造性思维”了。