AcWing 240. 食物链
原题链接
中等
作者:
Hustle
,
2021-05-14 16:17:16
,
所有人可见
,
阅读 215
抱歉只有代码和注释
C++ 代码
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 500010;
int n, m;
int p[N], d[N]; // d[x]即为 x 到根结点的距离
/*
维护每个点到根结点的距离,而根据此距离即可判定每个点之间的关系
因为该食物链中彼此只存在三种关系 : 1、吃 2、被吃 3、同类
而距离 % 3 之后即可判断该点和根结点的关系 :
1、d[x] % 3 = 0 ---> 和根结点同类
2、d[x] % 3 = 2 ---> 吃根结点
3、d[x] % 3 = 1 ---> 被根结点吃
而根据两个点和根结点之间的关系又能推断出彼此的关系 :
1、(d[x] - d[y]) % 3 = 0 ---> x、y同类
2、((d[x] - d[y]) % 3 + 3) % 3 == 2 ---> x 吃 y
//因为可能d[x] - d[y]后可能为-1或-2故+3再%3
3、((d[x] - d[y]) % 3 + 3 ) % 3 == 1 ---> x 被 y 吃
//因为可能d[x] - d[y]后可能为-1或-2故+3再%3
*/
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 ans = 0;
while (m -- ) {
int t, x, y;
scanf("%d%d%d", &t, &x, &y);
if (x > n || y > n) ans ++ ;
else {
int px = find(x), py = find(y);
if (t == 1) {
if (px == py && (d[x] - d[y]) % 3) ans ++ ;
else if (px != py) {
p[px] = py;
d[px] = d[y] - d[x];
}
}
else {
if (px == py && ((d[x] - d[y]) % 3 + 3) % 3 != 1) ans ++ ;
else if (px != py) {
p[px] = py;
d[px] = d[y] + 1 - d[x];
}
}
}
}
cout << ans << endl;
return 0;
}