POJ 1182 食物链

Time Limit: 1000MS Memory Limit: 10000K

【Description - 题目描述】

动物王国中有三类动物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），输出假话的总数。

【Input - 输入】

【Output - 输出】

第一行是两个整数N和K，以一个空格分隔。

以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。

若D=1，则表示X和Y是同类。

若D=2，则表示X吃Y。

只有一个整数，表示假话的数目。

【Sample Input - 输入样例】

【Sample Output - 输出样例】

100 7

1 101 1

2 1 2

2 2 3

2 3 3

1 1 3

2 3 1

1 5 5

【题解】

并查集

一共只有三种动物，对于不同种类的动物来说不是吃别人就是被吃。

每次[自身]与其他物种关系的变动都会影响到[天敌]与[食物]的关系

因此需要记录下[自身][天敌] [食物]三种关系

(百度一下后好像有着计算关系的方法……目测是把关系做了压缩)

因为看（shui）着（ping）爽（zha），所以把这三种关系都记录下来。

----------题外话

之前自己作死，除了[自身]初始化外其他都用0/-1表示，结果Debug了一周要死要活，最后结果总是差一点点点。

原来的代码看了很多遍，怀疑是判断条件和合并方式会冲突，Debug后bug滚雪球了……

果然自己这种渣渣水准还是作大死了，之后差点弃坑的时候看到了直接开int XX[3N]的记录方式，瞬间爆炸，哦不，醍醐灌顶，接着分分钟重写/改了一遍自己代码A了

---------回到正题

初始化的时候[自身][天敌][食物]最好是各不相同的值，这样写起来很轻松，否则如上……

这个时候[自身][天敌][食物]可以放在一个数组里面了，在同一个数组中查询与合并根的时候都很方便。

对于任意一个元素a

　　[自身]的位置= a

　　[天敌]的位置= a + n

　　[食物]的位置= a + 2n

以a b为例

　　a [天敌] [自身] [食物]

　　b [天敌] [自身] [食物]

a>n || b>n 可以直接为假了

对于第一种说法 1 a b

　　如果a吃b或b吃a则为假

　　否则合并a与b的[自身][天敌][食物]

对于第二种说法 2 a b

　　如果a b同源或b吃a则为假

　　否则合并 a[天敌]与b[食物]，a[自身]与b[食物]， a[食物]与[天敌]。

（这个感觉有点像矩阵的行列式，所以可以推倒出关系的求法？懒癌发作……）

【代码 C++】

 1 #include<stdio.h>
 2 int data[150005];
 3 int fid(int a){
 4     return data[a] == a ? a : data[a] = fid(data[a]);
 5 }
 6 bool isFriend(int a, int b){
 7     return fid(a) == fid(b);
 8 }
 9 int main(){
10     int  n, k, i, j, a, b, c, opt;
11     scanf("%d%d", &n, &k);
12     for (i = opt = 0, n *= 3; i < n; ++i) data[i] = i;
13     n /= 3;
14     while (k--){
15         scanf("%d%d%d", &c, &a, &b);
16         if (a>n || b > n){
17             ++opt;
18             continue;
19         }
20         if (c == 1){
21             if (isFriend(a + n, b) || isFriend(b + n, a)) ++opt;
22             else for (i = 0; i < 3; ++i, a += n, b += n) data[fid(a)] = fid(b);
23         }
24         else{
25             if (isFriend(a, b) || isFriend(a + n, b)) ++opt;
26             else for (i = 0, j = 1; i < 3; j = (i + 2) % 3, ++i) data[fid(a + n*i)] = fid(b + n*j);
27         }
28     }
29     printf("%d", opt);
30     return 0;
31 }