poj - 1182 - 食物链_综合

题意：动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是"1 X Y"，表示X和Y是同类。
第二种说法是"2 X Y"，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1）当前的话与前面的某些真的话冲突，就是假话；
2）当前的话中X或Y比N大，就是假话；
3）当前的话表示X吃X，就是假话。

你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。

题目链接：http://poj.org/problem?id=1182

——>>ORZ......WA了15次，每次WA后，总改改算法的格式，改来改去都是WA，太气人……对比别人的代码也看不出什么毛病，最后试着把循环输入改成一次输入，居然AC!无语呀……

这题用并查集来解决就行，但这里的集合中两元素是按能否确定相互之间的关系来判断是否属于同一集合的。记ren[x]为x与其父亲fa[x]之间的关系，我设为：ren[x] == 0 表示x与fa[x]同类，ren[x] == 1 表示x被fa[x]吃，ren[x] == 2 表示x吃fa[x]（子吃“父”，好二呀……）。

比如说：来条命令：1 1 2，1与2之前没有关系，现在说1与2同类，把2与1连起来，并赋上关系：ren[2] = 0；接着再来一条命令：2 2 3，2与3之前没有关系，现在说2吃3，把3与2的根连起来，关系传递之后可知3被1吃，于是赋上关系：ren[3] = 1；如果这时来一条命令：1 1 3，这里1与3在同一个集合中，判断其中的关系就是。

#include <iostream>
#include <cstdio>using namespace std;const int maxn = 50000 + 10;
int fa[maxn], ren[maxn];int find_set(int x)     //并查集查找函数
{if(x != fa[x]){int tmp = fa[x];fa[x] = find_set(fa[x]);ren[x] = (ren[x] + ren[tmp]) % 3;return fa[x];}else return x;
}
bool union_set(int D, int X, int Y)
{int root_X = find_set(X);       //取X的根int root_Y = find_set(Y);       //取Y的根if(D == 1)      //说是同类时{if(root_X == root_Y && ren[X] != ren[Y]) return 0;        //当X与Y已在同一个集合中时else if(root_X != root_Y)       //当X与Y不在同一个集合中时{fa[root_Y] = root_X;ren[root_Y] = (ren[X] - ren[Y] + 3) % 3;        //这里需要总结规律}}else     //说是X吃Y时{if(root_X == root_Y && (ren[X]+1)%3 != ren[Y]) return 0;        //当X与Y已在同一个集合中时else if(root_X != root_Y)       //当X与Y不在同一个集合中时{fa[root_Y] = root_X;ren[root_Y] = (ren[X] - ren[Y] + 4) % 3;        //这里需要总结规律}}return 1;
}
int main()
{int N, K, D, X, Y, i;cin>>N>>K;for(i = 1; i <= N; i++)     //初始化{fa[i] = i;ren[i] = 0;}int cnt = 0;while(K--){scanf("\n%d%d%d", &D, &X, &Y);if(X > N || Y > N || (D == 2 && X == Y))        //先排除后面两个条件{cnt++;continue;}if(!union_set(D, X, Y)) cnt++;}printf("%d\n", cnt);return 0;
}