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
只有一个整数，表示假话的数目。
我是 比如 A>B>C 对于每个点都有 P[X] V[X]表示 他被谁打败了 他打败了谁 他们之间的关系处理好后 比如A>B>C D>E>F 一旦 B 与E有关系 在不出错的前提下 然后 处理好 AD BE CF之间的关系
#include <iostream>
#include<cstdio>
#include<string.h>
using namespace std;
const int maxn=;
int per[maxn],p[maxn],v[maxn],N,K;
int fa(int a){ return per[a]=per[a]==a?a:fa(per[a]);}
bool jud1(int X,int Y){
if(X<||Y<||X>N||Y>N) return false;
int fx=fa(X),fy=fa(Y);
if(fx==p[fy]||fx==v[fy]||fy==p[fx]||fy==v[fx]) return false;
per[fy]=fx;
if(p[fx]!=&&p[fy]!=){ per[p[fy]]=p[fx];}
if(p[fx]==&&p[fy]!=)p[fx]=p[fy];
if(v[fx]!=&&v[fy]!=){ per[v[fy]]=v[fx];}
if(v[fx]==&&v[fy]!=) v[fx]=v[fy];
if(p[fx]!=){ p[p[fx]]=v[fx]; v[p[fx]]=fx; }
if(v[fx]!=){ p[v[fx]]=fx; v[v[fx]]=p[fx];}
return true;
}
bool jud2(int X,int Y){
if(X<||Y<||X>N||Y>N) return false;
int fx=fa(X),fy=fa(Y);
if(fx==fy||fx==v[fy]||fy==p[fx]) return false;
if(p[fy]!=)per[p[fy]]=fx;
if(v[fx]==)v[fx]=fy;
else per[fy]=v[fx];
if(p[fx]!=&&v[fy]!=) per[v[fy]]=p[fx];
if(p[fx]==&&v[fy]!=) p[fx]=v[fy];
if(p[fx]!=){ v[p[fx]]=fx;p[p[fx]]=v[fx];}
if(v[fx]!=){ p[v[fx]]=fx;v[v[fx]]=p[fx];} return true;
}
int main()
{
scanf("%d%d",&N,&K);
for(int i=;i<=N;i++){
per[i]=i; p[i]=v[i]=;
}
int num=;
for(int i=;i<K;i++){
int D,X,Y;
scanf("%d%d%d",&D,&X,&Y);
switch(D){
case : if(jud1(X,Y)==false) ++num; break;
case : if(jud2(X,Y)==false) ++num; break;
}
}
cout<<num<<endl; return ;
}
还有一种方法 带权并查集 队友说也可以
当 操作1 时 判断
1 这两个点在 同一个集合当中 他们到达 祖先的距离不同则出现错误 相同就正确
2 这两个点不在同一个集合当中 那么就得将这两个集合 合并 就是说 d[x]=（d[y]+d[fy])%3或者 d[y]=(d[x]+d[fx])%3 这样就保证了他们在一个集合当中的相同的位置 我们在并查集中做了一点小动作 保证了要修改的 d[fx] 或者d[fy] 为跟节点的子树 能够将相应的位置进行相应的改变
当操作2 时 判断
1 这两个的点在同一个集合当中 他们到达祖先的距离(d[x]+1)必须等于d[y] 否则就出现错误（因为我们保证了小的距离吃大的距离 自然最后记得模三）
2 这两个点在不懂得集合当中 那么也必须得河滨这两个集合 就是说 (d[x]+1)%3==(d[y]+d[fy])%3 可以推得 (d[x]+1-d[y]+3)==d[fy] 这样也保证了这两个点在相对的位置
#include <iostream>
#include<cstdio>
#include<string.h>
using namespace std;
const int maxn=;
int per[maxn],d[maxn];
int fin(int a){
if(per[a]==a)return a;
int t=per[a];
per[a]=fin(per[a]);
d[a]=(d[a]+d[t])%;
return per[a];
}
bool unionnode(int D,int x,int y){
int fx=fin(x),fy=fin(y);
if(D==){
if(fx==fy){ return d[x]==d[y]?true:false; }
if(d[x]==d[y]){ per[fy]=fx;return true;}
if(d[x]>d[y]){ d[fy]=(d[x]-d[y])%;per[fy]=fx; return true; }
d[fx]=(d[y]-d[x])%; per[fx]=fy; return true;
}
if(fx==fy){ return ((d[x]+)%)==d[y]?true:false; }
d[fy]=(d[x]-d[y]++)%;
per[fy]=fx;
return true;
}
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++){
per[i]=i;d[i]=;
}
int num=;
while(k--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(b>n||c>n||!unionnode(a,b,c)) num++;
}
printf("%d\n",num);
return ;
}