AcWing 240. 食物链
原题链接
中等
作者:
szywdwd
,
2021-05-24 15:52:33
,
所有人可见
,
阅读 235
#include <iostream>
using namespace std;
const int N = 50010;
int p[N], d[N];
int n, k;
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;
int res = 0;
for(int i = 1; i <= n; ++i) p[i] = i;
while(k--) {
int t, x, y;
cin >> t >> x >> y;
if(x > n || y > n) ++res;
else {
int px = find(x), py = find(y);
if(t == 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 << endl;
return 0;
}