膜大牛~写的超好，很详细，对于偏移量的确定也有讲解~
记得用scanf……cin……T了……orz
#include#include using namespace std;const int N = 5e4 + 5;struct node { int pre; int relation;};node p[N];int n, d,k, x, y,ans;void init(int n){ for (int i = 0; i <= n; i++) { p[i].pre = i; p[i].relation = 0; }}int findx(int x) //带劝啥的还是老老实实用递归……{ if (x == p[x].pre) return x; int temp = p[x].pre; p[x].pre = findx(temp); p[x].relation = (p[x].relation + p[temp].relation) % 3; return p[x].pre;}void unionn(int a, int b){ x = findx(a); y = findx(b); if (x != y) { p[y].pre = x; p[y].relation = (3+ p[a].relation+d-1-p[b].relation) % 3; } else { if (d == 1 && p[a].relation != p[b].relation) ans++; else if (d == 2 && (3 - p[a].relation + p[b].relation) % 3 != d - 1) ans++; }}int main(){ scanf("%d%d", &n, &k); init(n); ans = 0; while (k--) { scanf("%d%d%d", &d, &x,&y); if (x > n || y > n) ans++; else if (x == 2 && x == y) ans++; else unionn(x, y); } printf("%d\n", ans); return 0;}
这个要比食物链简单很多，只需要区分♂♀两类，emmmm其实上一个也可以用下面的方法做
#include#include using namespace std;int n, t,k, a, b,flag;int pre[4005];void init(int n){ for (int i=0; i <= 2*n; i++) pre[i] = i;}int findx(int x){ if (x == pre[x]) return x; int r = pre[x]; pre[x] = findx(r); return pre[x];}void unionn(int a, int b){ int x = findx(a), y = findx(b); if(x!=y) pre[y] = x;}bool judge(int x, int y){ if (findx(x) == findx(y)) return 0; else return 1;}int main(){ scanf("%d", &t); int cnt = 1; while (t--) { scanf("%d%d", &n, &k); init(n); flag = 0; for (int i = 0; i < k; i++) { scanf("%d%d", &a, &b); if (judge(a, b) || judge(a + n, b + n)) { unionn(a, b+n); unionn(a + n, b); } else flag = 1; } if(cnt!=1) //不要忘记换行orz puts(""); if (flag) { printf("Scenario #%d:\n", cnt++); puts("Suspicious bugs found!"); } else { printf("Scenario #%d:\n", cnt++); puts("No suspicious bugs found!"); } } return 0;}
