AcWing 240. 食物链 C++
原题链接
中等
作者:
LaChimere
,
2021-05-21 16:05:29
,
所有人可见
,
阅读 235
C++
#include <iostream>
using namespace std;
const int MAXSIZE = 50010;
int n, k, p[MAXSIZE], dist[MAXSIZE];
void init() {
for (int i = 0; i < MAXSIZE; ++i) {
p[i] = i;
}
}
int find(int x) {
if (p[x] != x) {
int tmp = find(p[x]);
dist[x] += dist[p[x]];
p[x] = find(p[x]);
}
return p[x];
}
bool legal(int x, int y) {
return !(x > n || y > n);
}
int main() {
int op, x, y, cnt = 0;
scanf("%d%d", &n, &k);
init();
while (k--) {
scanf("%d%d%d", &op, &x, &y);
if (!legal(x, y)) {
++cnt;
} else {
int px = find(x), py = find(y);
if (op == 1) {
if (px == py && (dist[x]-dist[y])%3) {
++cnt;
} else if (px != py) {
p[px] = py;
dist[px] = dist[y] - dist[x];
}
} else {
if (px == py && (dist[x]-dist[y]-1)%3) {
++cnt;
} else if (px != py) {
p[px] = py;
dist[px] = dist[y] - dist[x] + 1;
}
}
}
}
printf("%d\n", cnt);
return 0;
}