食物链的关系如下图
分别设
- k∈[1, n]
且 k 为 A类动物;
- k∈[n+1, 2*n]
且 k 为 B类动物;
- k∈[2*n+1, 3*n]
且 k 为 C类动物;
若 x 吃 y,则有如下3中可能
1. 如果 x 为 A 类型动物,那么 y 就为 B 类动物
2. 如果 x 为 B 类型动物,那么 y 就为 C 类动物
3. 如果 x 为 C 类型动物,那么 y 就为 A 类动物
merge(x, y+n) # 假设 x 为 A类动物的情况
merge(x+n, y+2*n) # 假设 x 为 B类动物的情况
merge(x+2*n, y) # 假设 x 为 C类动物的情况
参考文献
《挑战程序设计竞赛》P88~P90
代码
// CreateTime: 2019-11-09 20:07:53
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
using namespace std;
int n;
int k;
int D;
int x;
int y;
const int N = 15e4+10;
int parent[N];
void init() {
for (int i = 0; i <= 3*n; i++) {
parent[i] = i;
}
}
int find(int x) {
if (x != parent[x]) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void merge(int x, int y) {
int p1 = find(x);
int p2 = find(y);
parent[p2] = p1;
}
bool same(int x, int y) {
int p1 = find(x);
int p2 = find(y);
return p1 == p2;
}
bool D1(int x, int y) {
if (same(x, y+n) || same(x, y+2*n)) {
return false;
}
merge(x, y);
merge(x+n, y+n);
merge(x+2*n, y+2*n);
return true;
}
bool D2(int x, int y) {
if (same(x, y) || same(x, y+2*n)) {
return false;
}
merge(x, y+n);
merge(x+n, y+2*n);
merge(x+2*n, y);
return true;
}
int main(void) {
int res = 0;
cin >> n;
init();
cin >> k;
while (k--) {
cin >> D >> x >> y;
if (x > n || y > n) {
res += 1;
} else {
if (D == 1) {
if (D1(x, y) == false) {
res += 1;
}
}
if (D == 2) {
if (D2(x, y) == false) {
res += 1;
}
}
}
}
cout << res << endl;
return 0;
}