比如食物链中，更新时就是模3，需要找到权值之间的规律
另外还有一种方法，就是建立三倍的并查集，第一个并查集是A， 第二个并查集是B，第三个并查集是C，输入关系时，把同类和天敌输入，可以利用并查集的传递性，A->B B->C可以传递到关系C->A
这也正是题目所希望的
其次，建立集合时，关系是对称的，所以查询时只需查询一个集合里是否是同类，或者查询某两个集合是否是天敌就可以
#include<cstdio> #include<cstring> #include<iostream> using namespace std; int f[150005], ans = 0; int find(int x) { if (f[x] == -1) return x; f[x] = find(f[x]); return f[x]; } int ask(int a, int b) { a = find(a); b = find(b); if (a == b) return 1; return 0; } void add(int a, int b) { a = find(a); b = find(b); if (a != b) f[b] = a; } int main() { int n, k; scanf("%d%d", &n, &k); memset(f, -1, sizeof(f)); for (int i = 1; i <= k; i++) { int x, y, d; scanf("%d%d%d", &d, &x, &y); if (x > n || y > n || (d == 2 && x == y)) { ans++; } else { if (d == 1) { if (x == y)continue; if (ask(x, y + n) || ask(x + n, y + 2 * n) || ask(x + 2 * n, y) || ask(y, x + n)) { // 查询一个就可以 ans++; } else { add(x, y); add(x + n, y + n); add(x + 2 * n, y + 2 * n); } } if (d == 2) { if (x == y || (ask(x, y) || ask(x + n, y + n) || ask(x + 2 * n, y + 2 * n)) || ask(y, x + n)) { ans++; } else{ add(x, y + n); add(x + n, y + 2 * n); add(x + 2 * n, y); } } } } printf("%d\n", ans); return 0; }
原文：https://www.cnblogs.com/sunseabro/p/14546964.html