动物王国中有三类动物 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 句话有的是真的，有的是假的。
当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
- 当前的话与前面的某些真的话冲突，就是假话；
- 当前的话中 X 或 Y 比 N 大，就是假话；
- 当前的话表示 X 吃 X，就是假话。
你的任务是根据给定的 N 和 K 句话，输出假话的总数。
输入格式
第一行是两个整数 N 和 K，以一个空格分隔。
以下 K 行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中 D 表示说法的种类。
若 D=1，则表示 X 和 Y 是同类。
若 D=2，则表示 X 吃 Y。
输出格式
只有一个整数，表示假话的数目。
数据范围
1≤N≤50000,
0≤K≤100000
输入样例：
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
输出样例：
3思路：并查集维护根节点距离
我们先不考虑每两个动物x，y是什么关系，我们根据题目来判断；
如果x，y的取值在1~n，可以根据D的值判断是真话还是假话，或者判断将其变成真话；
假设x，y在一个集合 对于集合元素有h->a->b->c，h吃a，a吃b，b吃c，h到根节点距离为3，a到根节点距离为2，b到根节点距离为1；
可以推断出h和c是同类，他们之间的的距离为3%3=0，b被c吃，其到c的距离为2%3=2，a吃c，两者之间距离为1%3=1；
所以可以得出结论：如果x，y在一个集合 可以通过x和y到根节点的距离之差判断他们之间的关系，从而判断是真话还是假话；
如果距离之差%3=0，说明是同类，如果%3=1(x>y)，或者%3=-2(x<y)，说明x吃y；
如果不在同一集合，可以通过合并集合，调整其跟节点到新集合根节点的距离可以使其变成真话；
如果要是x，y不在同一集合，要使x，y为同类，则合并后(d[x]+d[p[x]]-d[y])%3=0，所以将其d[p[x]]变成d[y]-d[x]就行；
使x吃y也是同理：(d[p[x]]+d[x]-d[y]-1)%3=0，所以d[p[x]]=1+d[y]-d[x]；
d[p[x]]+d[x]-d[y]-1)%3=0与 x,y之差%3=1或者-2等价；
#include<iostream>
using namespace std;
const int N=5e5+10;
int p[N],d[N];//p数组存储x父节点，d存储x到根节点距离
int find(int x){
if(p[x]!=x){
int t=find(p[x]);//需要先存储根节点，不将父节点更新为根节点
//将父节点到根节点全部路径压缩指向根节点，同时更新父节点到根节点的距离
d[x]+=d[p[x]];//点x到根节点距离=x到父节点距离+父节点到根节点距离
p[x]=t;//更新父节点为根节点
}
return p[x];//返回根节点
}
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;++i) p[i]=i;
int res=0;//假话个数
while(k--){
int D,x,y;
cin>>D>>x>>y;
if(x>n||y>n) {
res++;//超出动物编号范围，为假
continue;
}
int px=find(x),py=find(y);//x，y的父节点
if(D==1){
if(px==py&&(d[x]-d[y])%3!=0) res++;//判断是否为同一集合且同类
else if(px!=py){//不为同一集合可变为同类
p[px]=py;
d[px]=d[y]-d[x];
}
}else{
if(px==py&&((d[x]-d[y])%3!=1&&(d[x]-d[y])%3!=-2)) res++;
//x吃y的两种情况，距离之差%3=-1或者2
else if(px!=py){
p[px]=py;
d[px]=1+d[y]-d[x];
}
}
}
cout<<res;
return 0;
}