AcWing 240. 食物链(并查集扩展域)
原题链接
中等
作者:
纸染
,
2021-02-08 20:13:28
,
所有人可见
,
阅读 249
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10, M = 3 * N;
int p[M];
int n, k;
// x : x的同类域
// x + n : x的捕食域
// x + n + n : x的天敌域
int Find(int x) {
return p[x] == x ? x : p[x] = Find(p[x]);
}
void Union(int x, int y) {
int root1 = Find(x), root2 = Find(y);
if (root1 != root2) {
p[root2] = root1;
}
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= 3 * n; i++) p[i] = i;
int cnt = 0;
while (k--) {
int op, x, y;
scanf("%d%d%d", &op, &x, &y);
if (x > n || y > n) {
cnt++; continue;
}
if (op == 1) {
if (Find(x + n) == Find(y) || Find(x + n + n) == Find(y)) cnt++;
// 判断x -> y : x 的捕食域 == y 的同类域
// 判断y -> x : x 的天敌域 == y 的同类域
else {
Union(x, y); // x 的同类域 == y 的同类域
Union(x + n, y + n); // x 的捕食域 == y 的捕食域
Union(x + n + n, y + n + n); // x 的天敌域 == y 的天敌域
}
}
else {
if (x == y) cnt++;
else if (Find(x) == Find(y) || Find(x + n + n) == Find(y)) cnt++;
// 判断 x == y : x 的同类域 == y 的同类域
// 判断 y -> x : x 的天敌域 == y 的同类域
else {
Union(x, y + n + n); // x 的同类域 == y 的天敌域
Union(x + n, y); // x 的捕食域 == y 的同类域
Union(x + n + n, y + n); // x 的天敌域 == y 的捕食域
}
}
}
printf("%d\n", cnt);
return 0;
}