POJ 1182 食物链 * 的简易版本
此题目POJ题目地址
这类问题共同点就是 1）分为固定几类，2）有类似一个环 男-->女--> 男
要点就是：1）思考集合与集合合并的时候两个根的关系
2）结点压缩的时候，结点与根的关系怎么根据边递推上去
#include<iostream>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=2000+5;
int p[maxn],r[maxn];
int getParent(int x){if(p[x]==x) return x;int xp=getParent(p[x]);r[x]=(r[x]+r[p[x]])%2;return p[x]=xp;
}
void merge(int xp,int yp,int x,int y) //x与y 一定不同所以要 +1
{p[xp]=yp;r[xp]=(r[y]+r[x]+1)%2;
}
int main()
{int T,kase=0;scanf("%d",&T);while(T--){int N,A,ok=1;scanf("%d%d",&N,&A);for(int i=1;i<=N;i++) {r[i]=0;p[i]=i;}int x,y,xp,yp;while(A--){scanf("%d%d",&x,&y);xp=getParent(x);yp=getParent(y); if(xp!=yp) merge(xp,yp,x,y);else if(r[x]==r[y]) ok=0; //忘加else结果一直WR } printf("Scenario #%d:\n%s\n\n",++kase,ok?"No suspicious bugs found!":"Suspicious bugs found!");}return 0;
}