此题按照《挑战程序设计竞赛（第2版）》P89的解法，不容易想到，但想清楚了代码还是比较直观的。
并查集模板（包含了记录高度的rank数组和查询时状态压缩）
1 const int MAX_N=50002*3; 2 int par[MAX_N]; 3 int rank[MAX_N]; 4 //初始化，根为自身，高度为0 5 void init(int scab) 6 { 7 for(int i=1;i<=scab;i++) 8 { 9 par[i]=i; 10 rank[i]=0; 11 } 12 } 13 //查找，途径的所有结点都直接连到根上 14 int find(int x) 15 { 16 if(par[x]==x) return x; 17 return par[x]=find(par[x]); 18 } 19 //合并，把短链连接到长链上，保持结点高度的相对关系 20 int unite(int x,int y) 21 { 22 x=find(x); 23 y=find(y); 24 if(x==y) return 0; 25 if(rank[x]<rank[y]) {par[x]=y; return 1;} 26 par[y]=x; 27 if(rank[x]==rank[y]) rank[x]++; 28 return 1; 29 }
并查集是用于维护“属于同一集合”的数据结构，然而这道题的“属于同一集合”并不指“是同类”，而是指“这几个情况若发生必然同时发生”。
我们从理解题意开始：
有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
想清楚了道理，代码就比较好理解了。注意由于从始至终只知道相对关系，同时维护了三种可能，所以判断矛盾的时候任选一种判断就可以了。
1 int main() 2 { 3 freopen("e.txt","r",stdin); 4 scanf("%d%d",&n,&k); 5 ans=0; 6 init(n*3); 7 while(k--) 8 { 9 scanf("%d%d%d",&d,&x,&y); 10 if(x>n||y>n) 11 { 12 ans++; 13 continue; 14 } 15 if(d==1) 16 {//若想成为同类，就不可能有x吃y或y吃x的关系 17 if(find(x)==find(y+n)||find(y)==find(x+n)) 18 ans++; 19 else 20 { 21 unite(x,y); 22 unite(x+n,y+n); 23 unite(x+2*n,y+2*n); 24 } 25 } 26 else if(d==2) 27 { 28 if(x==y) ans++; 29 //若想x吃y，则x,y不可能是同类，也不可能y吃x 30 else if(find(x)==find(y)||find(y)==find(x+n)) 31 ans++; 32 else 33 { 34 unite(x,y+n); 35 unite(x+n,y+2*n); 36 unite(x+2*n,y); 37 } 38 } 39 } 40 printf("%d\n",ans); 41 return 0; 42 }
OJ运行结果如下：
这道题使我对并查集有了新的认识，想清楚“同属一个集合”代表什么很重要，不一定就是题目限定的“属于同一种”。
分析问题的难度有时会大于编程的难度，如果说代码能力可以通过刷题习得，那么分析问题的能力真的需要足够的知识储备和一些“创造性思维”了。