本文共 2354 字，大约阅读时间需要 7 分钟。
此题按照《挑战程序设计竞赛（第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] 并查集是用于维护“属于同一集合”的数据结构，然而这道题的“属于同一集合”并不指“是同类”，而是指“这几个情况若发生必然同时发生”。
我们从理解题意开始：
有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 else20 {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吃x30 else if(find(x)==find(y)||find(y)==find(x+n))31 ans++;32 else33 {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运行结果如下：
这道题使我对并查集有了新的认识，想清楚“同属一个集合”代表什么很重要，不一定就是题目限定的“属于同一种”。
分析问题的难度有时会大于编程的难度，如果说代码能力可以通过刷题习得，那么分析问题的能力真的需要足够的知识储备和一些“创造性思维”了。
转载地址：http://byzgl.baihongyu.com/