题目链接： 题目描述： 动物王国中有三类动物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 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
思路上： 对于这道题，由于N和K很大，我们得高效的维护动物之间的关系，并快速判断是否产生了矛盾，可以采用并查集来维护“属于同一组”的信息，但是这一题除了A、B、C三类信息外，还有捕食关系，我们需要修改一下我们的并查集：
首先，我们并查集的大小为3 * N（对应每个动物可能属于A、B、C三种的情况），然后建立我们的维护规则： 语句输入为 1，101，1时： 1对应同一类，合并101和1，同时合并101+N和1+N，合并101+2N和1+2N（元素x，x + N, x + 2 * N分别代表x-A,x-B,x-C ）三种可能的情况；
语句输入为 2，101，1时： 2对应捕食，也有三种情况：x y => (A,B) OR x y => (B,C) OR x y => (C,A) 将所有可能的组合合并： 合并101和1+N； 合并101+N和1+2N； 合并101+2N和1；
依据以上两个规则的基础上，每次合并前再检查一下会不会出现如下矛盾：
x,y不在N的范围内t=1对应同一类,但是之前的语句已经将x,y划分为两类了t=2对应捕食,但是之前的语句已经将x,y划分为不能捕食的关系最终，我们维护的并查集每个组合代表的就是所有正确语句下，这些动物的分类可能情况~（每组要么都发生，要么都不发生）
由于并查集在STL标准库中没有实现，我们使用并查集一般都是自定义实现，一般为了防止并查集森林的树出现退化为链表，我们还记录高度，在合并时让最终树的高度尽量减小增长！
代码如下：
#include<cstdio> #define MAX_N 150005 //找了半天错，发现 MAX_N 要是 3 * N，之前用的是 N······ N -（0，50000] using namespace std; int par[MAX_N]; //每个节点的父亲编号 int rank[MAX_N]; // 节点高度 // 初始化n个元素 void init(int n){ for(int i = 0;i < n;++i){ par[i] = i; //每个节点的父亲一开始是他自己 rank[i] = 0; //开始高度都是0 } } //查询树的根 int find(int x){ return par[x]==x ? x : par[x]=find(par[x]); // if(par[x] == x){ //x是所在树的根，只有根的父亲为自己 // return x; // }else { // return par[x] = find(par[x]); // //向上找，并路径压缩， // //赋值表达式返回的是赋值后=左边的引用，实际上一般都是右边的值 // } } //合并x和y所属的集合 void unite(int x,int y){ //先判断他们是不是一个组 x = find(x); y = find(y); if(x == y) return; //高度改变原则：高度小的作为高度大的的子树 if(rank[x] < rank[y]) { par[x] = y; }else{ par[y] = x; if(rank[x] == rank[y]) rank[x]++; } } //判断x、y是否属于同一集合 bool same(int x,int y){ return find(x) == find(y); } //N 节点总数 K 输入语句数 int N,K; // 1 1 2 对应每一条输入语句，1代表同一类 2代表x吃y void solve() { scanf("%d %d",&N,&K); //初始化并查集 // 元素x，x + N, x + 2 * N分别代表x-A,x-B,x-C init(N * 3); int ans = 0;//错误语句数 for(int i = 0;i < K;++i){ int t,x,y; scanf("%d %d %d",&t,&x,&y); //t语句种类 x--,y--;//变为 0 —N-1 if( x >= N || y >= N) //编号错误！ { ans++; continue; } if(t == 1) //1代表同一类 { if( same(x,y + N) || same(x,y + 2 * N) ){ //x,y却不是同一类 ans++; } else{ //三个类，三种情况 unite(x,y); unite(x + N,y + N); unite(x + N * 2,y + N * 2); } } else if(t == 2){//2代表x吃y if(same(x,y) || same(x,y + 2 * N)) { //同类或者为AC类 ans++; } else{ //三个吃法，三种情况 unite(x,y + N); unite(x + N,y + 2 * N); unite(x + N * 2,y); } } } printf("%d\n",ans); } int main(){ solve(); }以上代码参考了《挑战程序设计竞赛（第二版）》P88，这里使用的是最通用的种类并查集来解题，实际上这道题更多的解法是 采用 “带权并查集”，具体解法：
/** 之前都是用的扩展并查集，不妨试试带权并查集 0表示同类， 1表示当前点能吃别人，2表示当前点被别人吃,需要注意的是如何更新value 对于路径压缩的更新带权： 0->0 ==> 0 0->1 ==> 1 0->2 ==> 2 1->1 ==> 2 1->0 ==> 1 1->2 ==> 0 2->0 ==> 2 2->1 ==> 0 2->2 ==> 1 规律为(value+par) % 3 同理对于合并也是 (s + value[y]) % 3 == (value[x] + ?) % 3 如何求？实际上 可以反向value[x](0-->0,1-->2,2-->1), 反向操作很关键 ? = (s + value[y] + (3 - value[x])) % 3 最后加入的时候如果已经存在关系了，检测权值是否一致 **/ #include<cstdio> #define MAX_N 50005 using namespace std; int par[MAX_N],value[MAX_N],ran[MAX_N]; int N,K; void init() { for(int i = 0; i <= N; ++i) { par[i] = i; value[i] = ran[i] = 0; } } int find(int x) { if(par[x] != x) { int t = par[x]; par[x] = find(par[x]); value[x] = (value[x] + value[t]) % 3; } return par[x]; } bool same(int x,int y) { return find(x) == find(y); } void unite(int x,int y,int v) { int px = find(x); int py = find(y); if(px == py) return; if(ran[px] < ran[py]){ //实际上维持高度平衡耗时跟 不维持差不了多少··· par[px] = py; value[px] = (v + value[y] + (3 - value[x])) % 3; }else{ par[py] = px; value[py] = (3 - v + value[x] + (3 - value[y])) % 3; if(ran[px] == ran[py]) ran[px]++; } } int main() { scanf("%d%d",&N,&K); init(); int res = 0; for(int i = 0; i < K; ++i) { int f,a,b; scanf("%d%d%d",&f,&a,&b); if (a > N || b > N || (f == 2 && a == b)) res++; else { if(same(a,b)) { // a到根，和b到根反向1 if((value[a] + 3 - value[b]) % 3 != f-1) { res++; } } else { unite(a,b,f-1); } } } printf("%d\n",res); return 0; }