好，经典扩展域并查集(冰茶几)。
因为有三个动物形成环(这不生物)，所以并查集开3倍。
x - y 表示同类，x - (y + n) 表示 y 吃 x
然后瞎搞搞即可。
思考：如果不是环，就是个A <- B <- C的食物链呢？如果还有A吃C呢？
据说是bitset
1 #include <cstdio> 2 3 const int N = 50010; 4 5 int fa[N * 3], n; 6 7 int find(int x) { 8 if(x == fa[x]) { 9 return x; 10 } 11 return fa[x] = find(fa[x]); 12 } 13 14 inline void merge(int x, int y) { 15 fa[find(x)] = find(y); 16 return; 17 } 18 19 inline bool check(int f, int x, int y) { 20 if(f == 1) { 21 return find(x) != find(y + n) && find(x) != find(y + n + n); 22 } 23 return find(x) != find(y) && find(y + n) != find(x); 24 } 25 26 inline void add(int f, int x, int y) { 27 if(f == 1) { 28 if(find(x) == find(y)) { 29 return; 30 } 31 merge(x, y); 32 merge(x + n, y + n); 33 merge(x + n + n, y + n + n); 34 } 35 else { 36 if(find(x + n) == find(y)) { 37 return; 38 } 39 merge(x + n, y); 40 merge(x + n + n, y + n); 41 merge(x, y + n + n); 42 } 43 return; 44 } 45 46 int main() { 47 int m; 48 scanf("%d%d", &n, &m); 49 for(int i = 1; i <= n * 3; i++) { 50 fa[i] = i; 51 } 52 int f, x, y, ans = 0; 53 for(int i = 1; i <= m; i++) { 54 scanf("%d%d%d", &f, &x, &y); 55 if(x > n || y > n) { 56 ans++; 57 continue; 58 } 59 else if(f == 2 && x == y) { 60 ans++; 61 continue; 62 } 63 if(check(f, x, y)) { 64 add(f, x, y); 65 } 66 else { 67 ans++; 68 } 69 } 70 printf("%d", ans); 71 return 0; 72 }