食物链
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 71707 | Accepted: 21240 |
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），输出假话的总数。
现有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
第一行是两个整数N和K，以一个空格分隔。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。
Output
只有一个整数，表示假话的数目。
Sample Input
100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5
Sample Output
3
Source
Solution
这个并查集是怎么回事？
我们把已经标记了关系的节点放在一个集合，也就是一棵树
我们声明rel[i]（也就是我也不懂的“偏移量”），
其实你可以理解为 I 到他爸爸的距离（爸爸到i这段链子的长度）qwq
那，距离怎么可能只有0，1，2呢？因为我将它mod 3啦
那……为什么要mod 3 ？
那样我们就可以确定 i 和他爸爸的关系啦
//P.S. 是不是有点似曾相识？好吧其实我想说google一年级数学题是一件很艰难的事情——
没错就是这尿性的东西。。。红吃黄，黄吃蓝，蓝又吃红 qwq——这大概就懂了把
下面是神奇的接链子，还有取模性质的运用
维护关系
读入2 x y表示x吃y时，我们需要合并x，y所在的两个集合就是两棵树
也就是把两条链子接起来
然后我找x,y爸爸时，在路径压缩时，顺便更新rel的值，
然后把x的爸爸指向y的爸爸，也要更新rel的值
判断真假话
根据2和3判断假话很简单，那根据1呢？
可以发现我们读入操作-1得到就是我们定义的rel的关系
于是
如果查询得出的结果与操作不同就是假话
否则按照操作合并集合，维护关系即可
例如：
当爸爸一样时，表示这两点之间存在关系，
(b到爸爸距离rel[b]-a到爸爸距离rel[a])%3可以得到a和b的关系 //可以看着上面一年级数学题的图脑补
//+3是为了防止出现小-大得到负数
为啥可以mod3值不会出错因为取模运算性质啊！
Codes
1 program foodchain; 2 var 3 n,k,i,x,a,b,ans:longint; 4 uset,rel:array[0..50000] of longint; 5 6 function find(app:longint):longint; 7 var 8 t:longint; 9 begin 10 if uset[app]=0 then exit(app); 11 t:=find(uset[app]); 12 rel[app]:=(rel[app]+rel[uset[app]]) mod 3; //因为原本app->uset[app]为rel[app] ,uset[app]->新的root为rel[uset[app]]，于是 13 uset[app]:=t; 14 find:=uset[app]; 15 end; 16 17 function union(a,b:longint):boolean; 18 var 19 p1,p2:longint; 20 21 begin 22 p1:=find(a); 23 p2:=find(b); 24 if p1=p2 then //之前已经存在关系 25 if (rel[b]-rel[a]+3) mod 3<>x-1 then exit(false) 26 else exit(true); 27 28 uset[p2]:=p1; 29 rel[p2]:=(rel[a]+3-rel[b]+x-1) mod 3; 30 exit(true); 31 end; 32 33 begin 34 readln(n,k); 35 36 for i:= 1 to k do 37 begin 38 readln(x,a,b); 39 if (a>n) or (b>n) or ((x=2) and (a=b)) then inc(ans) 40 else if union(a,b)=false then inc(ans); 41 end; 42 43 writeln(ans); 44 end.