食物链
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 54404 | Accepted: 15927 |
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
第一行是两个整数N和K，以一个空格分隔。 以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。 若D=1，则表示X和Y是同类。 若D=2，则表示X吃Y。
Output
只有一个整数，表示假话的数目。
Sample Input
100 71 101 1 2 1 22 2 3 2 3 3 1 1 3 2 3 1 1 5 5
Sample Output
3
Source
这是一个有趣的并查集题！首先，了解要遍历的并查集是一个怎样的一棵树。ta是这样的：这颗树中分为三类，ran[i] = 0,1,2 三类。A(ran[A] = 0) -> B(ran[B] = 1);B(ran[B] = 1) -> C(ran[C] = 2);C(ran[C] = 2) -> A(ran[A] = 0);ran[x]值也表示x与父亲节点fx的关系，在遍历和判断过程中有重要用途！遍历的过程：自然是两者的根不同，也就是他们之前没有任何联系，然后现在我们把ta俩 根据要求 联系起来;判断的过程：也就是两者在之前就有了什么联系，现在判断ta俩 现在的关系 是否与之前的关系 存在矛盾,矛盾则ans++;现在，有两个问题，怎么联系起来，怎么经行判断?联系和判断都要用到find的公式：ran[x] = (ran[x] + ran[fx])%3;(ran[x]表示x与fx的关系，ran[fx]表示fx与ffx的关系)由x和fx的关系和fx和ffx的关系自然可以推出x与ffx的关系，至于为什么是这个公式呢，你举几个例子便可验证，渣渣说不清= =!;(注意！find函数是从根开始更新ta的节点的);联系的公式：ran[fx] = (ran[y] - ran[x] + 3 + d)%3;首先知道：连接俩个不同根的树，是要从根连起来的pre[fx] = fy;在根据x与y的关系将fx更新出来;（这里也要注意！更新时只更新了根节点fx，并没有将整只树都更新出来，需要在find()中经行更新！并且此处fx是根节点，前面的那个fx,ffx是父亲节点和爷爷节点，自行理解哈。）判断的公式：if((ran[x] - ran[y] + 3)%3 != d-1);为什么是d-1呢？这就要看输入了：输入1表示同类，输入2表示吃与被吃关系，那么d-1表示 差值ran[x-y] = 0表示同类，差值ran[x-y] = 1表示吃与被吃;并且，之后unite函数中，也是带入了(d-1),联系公式中的d实质上是d-1!好啦！这就是我对这道题的理解，感觉还不够透彻，不知道你萌能不能看得懂，望大神指教哈！
#includeusing namespace std;int n;int pre[50005];int ran[50005];void init(){ for(int i = 1; i <= n; i++){ pre[i] = i; ran[i] = 0; }}int find(int x){ if(pre[x]==x) return x; int fx = pre[x]; pre[x] = find(pre[x]); ran[x] = (ran[x] + ran[fx])%3; return pre[x];}void unite(int x,int y,int d){ int fx = find(x); int fy = find(y); pre[fx] = fy; ran[fx] = (ran[y] - ran[x] + 3 + d)%3;}int main(){ int k; scanf("%d%d",&n,&k); init(); int ans = 0; while(k--){ int d,x,y; scanf("%d%d%d",&d,&x,&y); if(x > n || y > n){ ans++;continue; } int fx = find(x); int fy = find(y); if(fx == fy){ if((ran[x] - ran[y] + 3)%3 != d-1) ans++; } else unite(x,y,d-1); } printf("%d\n",ans); return 0;}