算法（食物链）

240. 食物链

•    题目

动物王国中有三类动物 A,B,C𝐴,𝐵,𝐶，这三类动物的食物链构成了有趣的环形。

A𝐴 吃 B𝐵，B𝐵 吃 C𝐶，C𝐶 吃 A𝐴。

现有 N𝑁 个动物，以 1∼N1∼𝑁 编号。

每个动物都是 A,B,C𝐴,𝐵,𝐶 中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 N𝑁 个动物所构成的食物链关系进行描述：

第一种说法是 1 X Y，表示 X𝑋 和 Y𝑌 是同类。

第二种说法是 2 X Y，表示 X𝑋 吃 Y𝑌。

此人对 N𝑁 个动物，用上述两种说法，一句接一句地说出 K𝐾 句话，这 K𝐾 句话有的是真的，有的是假的。

当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

1. 当前的话与前面的某些真的话冲突，就是假话；
2. 当前的话中 X𝑋 或 Y𝑌 比 N𝑁 大，就是假话；
3. 当前的话表示 X𝑋 吃 X𝑋，就是假话。

你的任务是根据给定的 N𝑁 和 K𝐾 句话，输出假话的总数。

输入格式

第一行是两个整数 N𝑁 和 K𝐾，以一个空格分隔。

以下 K𝐾 行每行是三个正整数 D，X，Y𝐷，𝑋，𝑌，两数之间用一个空格隔开，其中 D𝐷 表示说法的种类。

若 D=1𝐷=1，则表示 X𝑋 和 Y𝑌 是同类。

若 D=2𝐷=2，则表示 X𝑋 吃 Y𝑌。

输出格式

只有一个整数，表示假话的数目。

数据范围

1≤N≤500001≤𝑁≤50000,
0≤K≤100000

思路：

对于在同一颗树中的节点，根据节点和根节点之间的距离，在树内判断节点之间的关系。

对于不在同一个树内的节点，因为两个树当前没有相连，则代表两个树内的节点是没有任何关系的，则一定是真话，然后将两个树更新成一个大的树即可。

那么，是假话的可能有：

1.超过n

2.在同一个树里面，不满足对于规律（对于x吃x的情况，可以合并到其中）

本题要注意的点：

1.如何判断同一个树内的节点的关系，若x和y，（d[x]-d[y]）%3=0，同类；=1（x吃y），=2（y吃x）

2.如何合并两个树：默认x的树合到y的树里。如果是x和y同类的情况，则此时x原本的跟px，要更新其到跟的距离，距离应该满足d[x]-d[y]+d[px]=0,则d[px]=d[y]-d[x]。对于捕食关系类似。

3.对于查找当前树的跟，同时更新点x到跟的距离：首先先跟新其父节点到跟的距离，然后d[x]+=d[p[x]],p[x]是x原本的父节点。

#include<iostream>
#include<cstring>
using namespace std;const int N=1000010;
int ph[N],dis[N];
int n,k;
int find(int x)
{   if(x!=ph[x]){   int t=find(ph[x]);//此处必须先求出ph[x]那个点到跟的距离，放到dis[ph[x]]中，才能去求dis[x],先后顺序要注意。dis[x]+=dis[ph[x]];ph[x]=t;}return ph[x];
}int main()
{   scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)ph[i]=i;int ans=0;while(k--){int d,x,y;scanf("%d%d%d",&d,&x,&y);if(x>n||y>n){ans++;}else{if(d==1){int px=find(x),py=find(y);if(px==py && (dis[x]-dis[y])%3)ans++;else if(px!=py){ph[px]=py;dis[px]=dis[y]-dis[x];}}else{   int px=find(x),py=find(y);if(px==py && (dis[x]-dis[y]-1)%3)ans++;else if(px!=py){ph[px]=py;dis[px]=dis[y]-dis[x]+1;}}}}printf("%d\n",ans);return 0;
}