地址：http://poj.org/problem?id=1182
Description
Input
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
这个题非常经典，已经有很多这个题的题解了。
我看了这个大神的才懂的：https://blog.csdn.net/freezhanacmore/article/details/8767413 以下也是基本借鉴于他。并加了些个人理解，以便于交流。
定义r[]: 有0，1，2三个值。0：同类 1：被父节点吃 2：吃父节点
图：a->b表示b吃a
然后看图：
我们要求fy到fx的r[]，所以需要借助其他关系：fy->y->x->fx。所以公式为：(3-r[y]+d-1+r[x])%3，fy和fx，关系连接成功。
具体判断假话的条件见代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<set> using namespace std; const int maxn=5e4+10; int pr[maxn],r[maxn]; int n,m; void init() { for(int i=1;i<=n;i++) { pr[i]=i; r[i]=0; } } int find(int x) { if(x==pr[x]) return x; int fa=pr[x]; pr[x]=find(pr[x]); r[x]=(r[x]+r[fa])%3; return pr[x]; } void join(int a,int b,int d) { int fa=find(a),fb=find(b); if(fa!=fb) { pr[fb]=fa; r[b]=(3-r[b]+d-1+r[a])%3; } return ; } int main() { while(scanf("%d%d",&n,&m)) { init(); int d,a,b; int ans=0; while(m--) { scanf("%d%d%d",&d,&a,&b); if(a>n||b>n||(d==2&&a==b))//越界|本人吃本人 ans++; else if(find(a)==find(b)) { if(d==1&&r[a]!=r[b]) //在一棵树上。a,b同类，但是经查，对于同一根节点，r[a]不和r[b]一样，肯定是假话 ans++; if(d==2&&(r[a]+1)%3!=r[b]) //说a吃b，但是r[a]和r[b]并不满足公式，所以假话 ans++; } else //无法确定假话与否，就默认是真话，进行join()操作。 join(a,b,d); } cout<<ans<<endl; } }
原文：https://www.cnblogs.com/liyexin/p/12639956.html