记得第一次做这道题的时候，推关系感觉有点复杂，而且写完代码后一直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=50010; int father[maxn]; int rel[maxn];//rel[i]表示i相对根节点的关系，0:与根节点同类；1:被根节点吃；2:吃根节点 int n,k; void init(){ for(int i=0;i<maxn;i++){ father[i]=i; rel[i]=0; } } 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])%3; return father[x]; } void Union(int x,int y,int fx,int fy,int d){ father[fy]=fx; rel[fy]=(3-rel[y]+d+rel[x])%3; } int main() { int ans=0,d,x,y; //ans统计假话的个数 scanf("%d%d",&n,&k); init();//又忘记初始化了啊啊啊 for(int i=1;i<=k;i++){ scanf("%d%d%d",&d,&x,&y); //若有大于n，则为假话 if(x>n||y>n){ ans++; continue; } if(d==1){ d=0; } else{ d=1; //若x吃x，则是假的 if(x==y){ ans++; continue; } } int fx=find_root(x); int fy=find_root(y); if(fx==fy){ int t=(rel[y]+3-rel[x])%3; if(t!=d){ ans++; } } else{ Union(x,y,fx,fy,d); } } printf("%d ",ans); return 0; }