转载请注明出处，谢谢：http://www.cnblogs.com/KirisameMarisa/p/4298148.html ---by 墨染之樱花
题目链接：http://poj.org/problem?id=2492
题目描述：找基佬游戏（汗-_-b）有个hentai科学家研究虫子种群，不断地给出二元组xy，表示x和y是异性交往，但是可能会出现矛盾（找到基佬），比如1与2是异性恋，2与3是异性恋，却又告诉你1和3是异性恋。问种群中存不存在基佬败类
思路：与poj1182“食物链”几乎一样，还简单一点，毕竟只有两类物品。par[i]表示父节点，d[i]表示偏移量，0为同性，1为异性。不过要注意的一点是所有合并的过程要对二取模，比如x找到根结点s的路径是x1,x2...xn那么，d[x]=(d[x]+d[x1]+...d[xn])%2。poj1703与此题几乎一样，代码改改就能交了
#include <iostream> #include <ios> #include <iomanip> #include <functional> #include <algorithm> #include <vector> #include <sstream> #include <list> #include <queue> #include <deque> #include <stack> #include <string> #include <set> #include <map> #include <cstdio> #include <cstdlib> #include <cctype> #include <cmath> #include <cstring> #include <climits> using namespace std; #define XINF INT_MAX #define INF 1<<30 #define MAXN 2000+10 #define eps 1e-8 #define zero(a) fabs(a)<eps #define sqr(a) ((a)*(a)) #define MP(X,Y) make_pair(X,Y) #define PB(X) push_back(X) #define PF(X) push_front(X) #define REP(X,N) for(int X=0;X<N;X++) #define REP2(X,L,R) for(int X=L;X<=R;X++) #define DEP(X,R,L) for(int X=R;X>=L;X--) #define CLR(A,X) memset(A,X,sizeof(A)) #define IT iterator #define PI acos(-1.0) #define test puts("OK"); #define _ ios_base::sync_with_stdio(0);cin.tie(0); typedef long long ll; typedef pair<int,int> PII; typedef priority_queue<int,vector<int>,greater<int> > PQI; typedef vector<PII> VII; typedef vector<int> VI; #define X first #define Y second int par[MAXN]; int d[MAXN]; int n,m; int find(int x) { int s,tot=0; for(s=x;par[s]>=0;s=par[s]) tot+=d[s]; while(s!=x) { int temp=par[x]; par[x]=s; int tmp=d[x]; d[x]=tot%2; tot-=tmp; x=temp; } return s; } int main() {_ int T; scanf("%d",&T); REP(k,T) { scanf("%d%d",&n,&m); CLR(par,-1);CLR(d,0); bool flag=1; REP(i,m) { int x,y; scanf("%d%d",&x,&y); if(flag) { int r1=find(x),r2=find(y); if(r1!=r2) { par[r2]=r1; d[r2]=!(d[x]^d[y]); } else if(!(d[x]^d[y])) flag=0; } } printf("Scenario #%d: ",k+1); if(!flag) printf("Suspicious bugs found! "); else printf("No suspicious bugs found! "); } return 0; }
附poj1703 “Find them, Catch them”代码（c++OLE，g++AC...-_-b）：
#include <iostream> #include <ios> #include <iomanip> #include <functional> #include <algorithm> #include <vector> #include <sstream> #include <list> #include <queue> #include <deque> #include <stack> #include <string> #include <set> #include <map> #include <cstdio> #include <cstdlib> #include <cctype> #include <cmath> #include <cstring> #include <climits> using namespace std; #define XINF INT_MAX #define INF 1<<30 #define MAXN 100000+10 #define eps 1e-8 #define zero(a) fabs(a)<eps #define sqr(a) ((a)*(a)) #define MP(X,Y) make_pair(X,Y) #define PB(X) push_back(X) #define PF(X) push_front(X) #define REP(X,N) for(int X=0;X<N;X++) #define REP2(X,L,R) for(int X=L;X<=R;X++) #define DEP(X,R,L) for(int X=R;X>=L;X--) #define CLR(A,X) memset(A,X,sizeof(A)) #define IT iterator #define PI acos(-1.0) #define test puts("OK"); #define _ ios_base::sync_with_stdio(0);cin.tie(0); typedef long long ll; typedef pair<int,int> PII; typedef priority_queue<int,vector<int>,greater<int> > PQI; typedef vector<PII> VII; typedef vector<int> VI; #define X first #define Y second int par[MAXN]; int d[MAXN]; int n,m; int find(int x) { int s,tot=0; for(s=x;par[s]>=0;s=par[s]) tot+=d[s]; while(s!=x) { int temp=par[x]; par[x]=s; int tmp=d[x]; d[x]=tot%2; tot-=tmp; x=temp; } return s; } int main() {_ int T; scanf("%d",&T); REP(k,T) { scanf("%d%d",&n,&m); CLR(par,-1);CLR(d,0); REP(i,m) { char c; int x,y; scanf("%s%d%d",&c,&x,&y); int r1=find(x),r2=find(y); if(c=='D') { if(r1!=r2) //成环不管矛不矛盾直接舍弃，否则会反复迭代造成TLE { par[r2]=r1; d[r2]=!(d[x]^d[y]); } } else { if(r1!=r2) printf("Not sure yet. "); else if(d[x]^d[y]) printf("In different gangs. "); else printf("In the same gang. "); } } } return 0; }