240.食物链
动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。
A吃B, B吃C,C吃A。
现有N个动物,以1-N编号。
每个动物都是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句话,输出假话的总数。
思想
维护两个数组,p[i] 表示i结点的根结点。d[i] 表示i结点到根结点的距离。利用两点之间的距离关系来表示题目中要求的食物链关系,设x与y点到同一个根结点的距离分别为d[x]和d[y],则若(d[x] - d[y]) % 3 == 0 表示x与y为同一物种,若模3等于1 则表示x 可以吃y,模3等于2 则表示y 可以吃x。
find函数既完成了查找根结点的工作,也完成了压缩路径的工作,则每次在压缩路径的时候,要将当前表示x到上一个结点的距离d[x] 更新为到根结点的距离,即d[x] = d[x] + d[p[x]]。
代码
#include <iostream>
using namespace std;
const int N = 500010;
int n,m;
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 >> m;
for(int i = 1; i <= n; i++){
p[i] = i;
}
int res = 0;
while(m--){
int t,x,y;
cin >> t >> x >> y;
if(x > n || y > n)
{
res++;
continue;
}
int px = find(x),py = find(y);
if(t == 1){
if(px == py && (d[x] - d[y]) % 3)
res++;
// 此处表示x与y有相同的根结点,但是与根结点的距离模3不一样,说明不是同一物种
else if(px != py){
p[px] = py;
d[px] = d[y] - d[x];
// 由于x与y的根结点不同,因此让x的根结点指向py,
// 需要记录d[px]的值使得x到当前根结点py的距离模3 等于y到py的距离模3.
// 即(d[x] + d[px] - d[y]) % 3 == 0。
}
}else{
if(px == py && (d[x] - d[y] - 1) % 3)
res++;
// 此处表示x与y有相同的根结点,但(d[x] - d[y]) % 3不等于1,表明x并不能吃y
else if(px != py){
p[px] = py;
d[px] = d[y] + 1 - d[x];
// 计算原理同上
}
}
}
cout << res << endl;
return 0;
}