AcWing 240. 食物链
原题链接
中等
作者:
Asteroid.W
,
2021-08-30 11:06:35
,
所有人可见
,
阅读 254
#include<iostream>
using namespace std;
const int N = 50010;
int n, k, res; // res是假话的个数
int p[N]; //父节点
int d[N]; //到父节点的距离
int find(int x) // 返回根节点
{
if(p[x] != x){ // 如果p[x]不是根节点。find()函数进行了路径压缩,当查询某个节点 i 时,如果 i 的父节点不为根节点的话,就会进行递归调用,将 i 节点沿途路径上所有节点均指向父节点,此时的 d[i] 存放的是 i 到父节点,也就是根节点的距离
int t = find(p[x]); //先把父节点及以上压缩到树根
d[x] += d[p[x]]; //d[x]是到根节点的距离 等于 它到父节点的距离加上父节点到根节点的距离
p[x] = t; //将p的父节点指向根节点
}
return p[x];
}
int main()
{
cin >> n >> k; // n是动物个数,k是说话个数
for(int i = 1; i <= n; i++) p[i] = i; // 每个点初始化
while(k--){
int v, x, y; // v是说法的种类
cin >> v >> x >> y;
if(x > n || y > n) res++; // 大于动物总数,假话
else{
int rx = find(x), ry = find(y); // 找到根节点,又找到到根节点的距离
if(v == 1){ // 1表示x和y是同类
//假话
if(rx == ry && (d[y] - d[x]) % 3 != 0) res++; // x和y的根节点相同,在同一个树中,并且他们到根节点的距离模3不相等(这里的计算化简了),说明不是同类是假话。
//真话
else if(rx != ry){ //当前不在同一集合中,无法判定为假。故为真,应加入同一树(集合)表示存在同类关系
p[rx] = ry; //让y的根节点成为x的根节点的父节点。合并两个树。
d[rx] = d[y] - d[x]; //x和y同类,则x和y 模3距离相同。x原来的根节点到x新的根节点的距离 与 y到根节点的距离相同。距离相同,模3同余。(d[x]+d[rx]-d[y])%3 = 0,由于判断时都针对mod 3,故mod 3可省略
}
}
else if(v == 2){ // 2表示x吃y
if(x == y) res++;// 同类吃同类,x吃y 此话为假
else if(rx == ry && (d[x] - d[y] - 1) % 3) res++; // 这里合并了,(d[x] - d[y] - 1) % 3意思是:x到根节点的距离模3 比 y到根节点的距离模3 是否大1个数。
else if(rx != ry){ // x和y不在同一个树(集合)里
p[rx] = ry;
d[rx] = d[y] + 1 - d[x]; // x吃y,距离多1。
}
}
}
}
cout << res << endl;
}