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
最终AC代码：
#include<iostream>using namespace std;const int MAX_N = 50010;int set[MAX_N];int r[MAX_N];void init(int n){for (int i = 0; i <= n; i++){set[i] = i;r[i] = 0;}}//原理如下：//首先，集合里的每个点我们都记录它与它这个集合(或者称为子树)的根结点的相对关系relation。0表示它与根结点为同类，1表示它吃根结点，2表示它被根结点吃。//那么判断两个点a, b的关系，我们令p = Find(a), q = Find(b)，即p, q分别为a, b子树的根结点。//1. 如果p != q，说明a, b暂时没有关系，那么关于他们的判断都是正确的，然后合并这两个子树。这里是关键，如何合并两个子树使得合并后的新树能保证正确呢？//这里我们规定只能p合并到q(刚才说过了，启发式合并的优化效果并不那么明显，如果我们用启发式合并，就要推出两个式子，而这个推式子是件比较累的活…所以//一般我们都规定一个子树合到另一个子树)。那么合并后，p的relation肯定要改变，那么改成多少呢？这里的方法就是找规律，列出部分可能的情况，就差不多能推出//式子了。这里式子为 : tree[p].relation = (tree[b].relation – tree[a].relation + 2 + d) % 3; 这里的d为判断语句中a, b的关系。还有个问题，我们是否需要//遍历整个a子树并更新每个结点的状态呢？答案是不需要的，因为我们可以在Find()函数稍微修改，即结点x继承它的父亲(注意是前父亲，因为路径压缩后父亲就会改变)，//即它会继承到p结点的改变，所以我们不需要每个都遍历过去更新。//2. 如果p = q，说明a, b之前已经有关系了。那么我们就判断语句是否是对的，同样找规律推出式子。即if((tree[b].relation + d + 2) % 3 != tree[a].relation), //那么这句话就是错误的。//3. 再对Find()函数进行些修改，即在路径压缩前纪录前父亲是谁，然后路径压缩后，更新该点的状态(通过继承前父亲的状态，这时候前父亲的状态是已经更新的)。int cha(int x){if (x == set[x])return x;int tx = cha(set[x]);//关键,此处要理解，若上一次合并两个高度为2的树，合并后一棵树高度变为3，则在下一次查询时完成所有结点状态的更新。//查找中的更新 压缩路径中的更新r[x] = (r[x] + r[set[x]]) % 3;//return tx; 错误，要完成路径的更新return set[x] = tx;}void unite(int x, int y, int type){int tx = cha(x);int ty = cha(y);set[ty] = tx;//合并这两棵树r[ty] = (r[x] + type – 1 – r[y] + 3) % 3;//关键，修改相对关系return;}int main(){#ifdef ONLINE_JUDGE#elsefreopen("D:\\in.txt", "r", stdin);freopen("D:\\out.txt", "w", stdout);#endifint n(0), m(0);scanf("%d%d", &n, &m);init(n);int type(0), x(0), y(0);int ans(0);for (int i = 1; i <= m; i++){scanf("%d%d%d", &type, &x, &y);if (x > n || y > n || (type == 2 && x == y)){ans++;continue;}if (cha(x) == cha(y))//在同一棵树中{if ((r[y] – r[x] + 3) % 3 != (type – 1)){ans++;}}else{(unite(x, y, type));//不在一棵树中，则合并}}printf("%d\n", ans);}
代码如下：
#include<iostream>#include<vector>#include<algorithm>#include<functional>#include<iterator>#include<cstdio>#include<queue>using namespace std;//并查集const int MAX_N = 50010;const int MAX_K = 100010;int set[MAX_N*3];//父亲int height[MAX_N*3];//树的高度int T[MAX_K],X[MAX_K],Y[MAX_K];//并查集//初始化n个元素void init(int n){for (int i = 0; i < n; i++){set[i] = i;//set[x]==x时，x是所在树的根height[i] = 0;}}//查 查询x所在树的根int cha(int x){int r = x;while (set[r] != r)r = set[r];int i = x;int j(0);while (i != r)//路径压缩{j = set[i];set[i] = r;i = j;}return r;}//并 合并x和y所属的集合void unite(int x, int y){x = cha(x);y = cha(y);if (x == y)return ;if (height[x] < height[y]){set[x] = y;}else{set[y] = x;if (height[x] == height[y])height[x]++;}}//判断x和y是否属于同一个集合bool same(int x, int y){return cha(x) == cha(y);}int main(){#ifdef ONLINE_JUDGE #elsefreopen("D:\\in.txt", "r", stdin);freopen("D:\\out.txt", "w", stdout);#endif // ONLINE_JUDEGint n(0), k(0);int ans(0);scanf("%d%d", &n, &k);for (int i = 0; i < k; i++){scanf("%d%d%d", &T[i], &X[i], &Y[i]);}//初始化并查集，元素x,x+n,x+2*n分别代表x-A,x-B,x-Cinit(n * 3);ans = 0;for (int i = 0; i < k; i++){int t = T[i];//信息的类型int x = X[i] – 1;int y = Y[i] – 1;//把输入变成0–N-1的范围//不正确的编号if (x < 0 || y < 0 || x >= n || y >= n){ans++;continue;}if (t == 1)//“x 和 y 属于同一类”的信息{if (same(x,y+n)||same(x,y+2*n)){ans++;}else{unite(x, y);unite(x + n, y + n);unite(x + n * 2, y + n * 2);}}else// "x吃y的信息"{if (same(x, y) || same(x, y + 2 * n)){ans++;}else{unite(x, y + n);unite(x + n, y + 2 * n);unite(x + 2 * n, y);}}}printf("%d\n", ans);return 0;}
其他的解题思路：
今天做了经典的食物链，在总结网上其它做法后，小结如下：
题意：一共就三种动物，如果A吃B，B吃C==》C吃A；
一个人的天地是冷得连呼吸都会寂寞的颤栗，而麻烦，
