记得第一次做这道题的时候，推关系感觉有点复杂，而且写完代码后一直WA，始终找不出错误。 在A了十几道并查集后，再做这道题，发现太小儿科了。发现原来之所以WA，就在于查找根节点时，没有同步更新子节点相对根节点的关系。现在对并查集的感觉就在于，并查集的精髓就在于如何更新子节点与父节点的相对关系。
0:与根节点同类；1:被根节点吃；2:吃根节点
如何更新：
设x的根节点为fx，y的根节点为fy。
1.若fx!=fy:
合并fx、fy(将fy的父亲设为fx)，那么要更新fy相对fx的关系。
fy相对y的关系为：3-rel[y]，y相对x的关系为d-1(d即为数据中的d)，x相对fx的关系为rel[x]。
那么fy相对fx的关系即为：(3-rel[y]+d-1+rel[x])%3。
2.若fx==fy:
那么则要判断由此推算出的y相对x的关系，是否等于数据给出的d-1。若不相等，则是假话。
y相对fy/fx的关系为rel[y]，fy/fx相对x的关系为3-rel[x]，
则y相对x的关系为：(rel[y]+3-rel[x])%3。
至于其他判断它为假话的条件就很好办了。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm> using namespace std;
const int maxn=;
int father[maxn];
int rel[maxn];//rel[i]表示i相对根节点的关系，0:与根节点同类；1:被根节点吃；2:吃根节点
int n,k;
void init(){
for(int i=;i<maxn;i++){
father[i]=i;
rel[i]=;
}
} int find_root(int x){
if(father[x]==x)
return x;
int tmp=father[x];
father[x]=find_root(father[x]);
rel[x]=(rel[x]+rel[tmp])%;
return father[x];
}
void Union(int x,int y,int fx,int fy,int d){
father[fy]=fx;
rel[fy]=(-rel[y]+d+rel[x])%;
}
int main()
{
int ans=,d,x,y; //ans统计假话的个数
scanf("%d%d",&n,&k);
init();//又忘记初始化了啊啊啊
for(int i=;i<=k;i++){
scanf("%d%d%d",&d,&x,&y);
//若有大于n，则为假话
if(x>n||y>n){
ans++;
continue;
} if(d==){
d=;
}
else{
d=;
//若x吃x，则是假的
if(x==y){
ans++;
continue;
}
}
int fx=find_root(x);
int fy=find_root(y);
if(fx==fy){
int t=(rel[y]+-rel[x])%;
if(t!=d){
ans++;
}
}
else{
Union(x,y,fx,fy,d);
}
}
printf("%d\n",ans);
return ;
}
