题解 P2024 【食物链】
这道题的特殊之处在于对于任意一个并查集，只要告诉你某个节点的物种，你就可以知道所有节点对应的物种。
比如一条长为4的链 甲->乙->丙->丁 ，我们知道乙是A物种。那么甲一定是B物种，因为A只吃B物种，不吃C物种或是自己的同类。同样的丙一定是C物种，丁是B物种。
也就是说，每一条链上都是A、B、C物种循环，这也是我们寻找不合逻辑的假话的出发点。
我们可以定义数组d[i]表示节点i到根节点距离mod3的结果帮助解题。
我们统计谎话的数量，那么我们把谎话这样分类：
第一类叫弱智的谎话，包括
（1）自己吃自己的同类是谎话，表述为d==2&&x==y（其中x y是我们读入的量）；
（2）编号超出限制，表述为x>n||y>n。 第二类叫不弱智的谎话，包括d==1和d==2这样两类。
（1）d==1。
我们先要考虑x y是否在同一个并查集中，这是判断真假话的前提。
如果x y 不在同一个并查集中，那么关于他们的任何表述都可以是真的。
比如两条链：1->2->3->4->5 6->7->8->9
如果我说1和6是同类，那么自然地，2与7，3与8，4与9成为同类。
我们任意的选取两个数是同类都是符合的。
下面我们要做的就是把两个并查集合并。
d[f[x]]=(d[y]-d[x]+3)%3;//关于距离
f[f[x]]=f[y];//关于父亲
如果x y在同一个并查集中，那么违反距离关系的话一定是假话。
d[x]!=d[y]//关于距离
（2）d==2。
还是先看x y是否在一个并查集中，如果不在，那么合并并查集；如果在，那么根据距离关系找出假话。
下面是我的代码：
#include<iostream>
#include<cstdio>
using namespace std;
int f[50005],d[50005],n,k,d1,x,y,ans;
int find(int x)//寻找祖先的函数
{
if(x!=f[x])
{
int xx=f[x];
f[x]=find(f[x]);
d[x]=(d[x]+d[xx])%3;
}
return f[x];
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{f[i]=i;d[i]=0;}
for(int i=1;i<=k;i++)
{
scanf("%d%d%d",&d1,&x,&y);
if((d1==2&&x==y)||(x>n||y>n))
{ans++;continue;}//弱智的假话
if(d1==1)
{
if(find(x)==find(y))//x y在一个并查集中，找假话
{if(d[x]!=d[y]) ans++;}//关于距离
else//x y不在一个并查集中，合并并查集
{
d[f[x]]=(d[y]-d[x]+3)%3;//关于距离
f[f[x]]=f[y];//关于父亲
}
}
if(d1==2)
{
if(find(x)==find(y))//x y在一个并查集中，找假话
{if(d[x]!=(d[y]+1)%3) ans++;}//关于距离
else//x y不在一个并查集中，合并并查集
{
d[f[x]]=(d[y]-d[x]+4)%3;//关于距离
f[f[x]]=f[y];//关于父亲
}
}
}
printf("%d\n",ans);
}