食物链解读

[NOI2001] 食物链

题目描述

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

现有 $N$ 个动物，以 $1\sim N$ 编号。每个动物都是 $A,B,C$ 中的一种，但是我们并不知道它到底是哪一种。

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

• 第一种说法是 1 X Y，表示 $X$ 和 $Y$ 是同类。
• 第二种说法是2 X Y，表示 $X$ 吃 $Y$。

此人对 $N$ 个动物，用上述两种说法，一句接一句地说出 $K$ 句话，这 $K$ 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

• 当前的话与前面的某些真的话冲突，就是假话；
• 当前的话中 $X$ 或 $Y$ 比 $N$ 大，就是假话；
• 当前的话表示 $X$ 吃 $X$，就是假话。

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

输入格式

第一行两个整数，$N,K$，表示有 $N$ 个动物，$K$ 句话。

第二行开始每行一句话（按照题目要求，见样例）

输出格式

一行，一个整数，表示假话的总数。

样例 #1

样例输入 #1

100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

样例输出 #1

3

提示

对于全部数据，$1\le N\le 5\times 10^4$，$1\le K\le 10^5$。

这是一道没本事的中等题，看过的人都知道用指针做。不过在实操的过程中有几个小点需要注意：
先看代码：

#include<iostream>
#include<algorithm>
using namespace std;
const int N=50010;
int  n,k,res;
int p[N],d[N];
int find(int x)
{if(p[x]!=x){int t=find(p[x]);d[x]+=d[p[x]];p[x]=t;}return p[x];
}
int main()
{cin>>n>>k;for(int i=1;i<=n;i++){p[i]=i;}while(k--){int m,x,y;cin>>m>>x>>y;if(x>n||y>n){res++;}else{int px=find(x),py=find(y);if(m==1){if(px==py&&(d[x]-d[y])%3)res++;else if(px!=py){p[px]=py;d[px]=d[y]-d[x];}}else{if(px==py&&(d[x]-d[y]-1)%3)res++;else if(px!=py){p[px]=py;d[px]=d[y]-d[x]+1;}}}}cout<<res;return 0;
}

小点1

d[px]=d[y]-d[x] 和 d[px]=d[y]-d[x]+1 是怎么来的？
根据指针指向，m1时，d[x]+?=d[y]，?=d[y]-d[x]；m2时，d[x]+?-1=d[y]，?=d[y]-d[x]+1。

小点2

find 函数

int find(int x)
{if(p[x]!=x){int t=find(p[x]);d[x]+=d[p[x]];p[x]=t;}return p[x];
}

这样是对的，大家都能看出来，但有没有人觉得 t 有些多余？
想改成这样：

int find(int x)
{if(p[x]!=x){d[x]+=d[p[x]];p[x]=find(x);}return p[x];
}

但这样是过不了的
下面的代码却能过：

int find(int x)
{if(p[x]!=x){int t=find(p[x]);d[x]+=d[p[x]];p[x]=find(p[x]);}return p[x];
}

发现问题所在了吗？
一般情况下，t 确实无用，但这是递归，p[x] 要不要变，要的，但在什么时候变？
一定要在先 find(p[x]) 再更新 d[x]，为什么？
因为这是递归，递归什么特点？
从最后一种情况慢慢往前推，因为你没有办法保证 d[p[x]] 一开始一定存在，所以需要不断地更新 d[x]。