http://acm.pku.edu.cn/JudgeOnline/problem?id=2492
ms很邪惡 很ws的題目，題目給出了n組bug 相好的記錄讓
你在一大堆bug中讓你找出可疑的同性戀者。夠邪惡吧！！
簡(jiǎn)單并的并查集。
Source Code
| Problem: 2492 |
|
User: lovecanon |
| Memory: 228K |
|
Time: 735MS |
| Language: C++ |
|
Result: Accepted |
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int father[2000+1],mark[2000+1],rank[2000+1];
int find(int t){
int tmp=t,flag=mark[t];
while(father[tmp]!=tmp){
flag^=mark[father[tmp]];
tmp=father[tmp];
}
father[t]=tmp;
mark[t]=flag;
return tmp;
}
int main()
{
int i,T,cases=1;
scanf("%d",&T);
while(T--){
int N,M;
scanf("%d%d",&N,&M);
for(i=1;i<=N;i++) {father[i]=i;mark[i]=0;rank[i]=0;}
int a,b,flag=0;
while(M--){
scanf("%d%d",&a,&b);
int x=find(a),y=find(b);
if(flag==0 && x==y && mark[a]==mark[b]) flag=1;
else if(flag==0 && x!=y){
if(rank[x]>rank[y]){
father[x]=y;
mark[x]=!(mark[a]^mark[b]);
}
else{
father[y]=x;
mark[y]=!(mark[a]^mark[b]);
if(rank[x]==rank[y]) rank[x]++;
}
}
}
if(flag==1) printf("Scenario #%d:\nSuspicious bugs found!\n\n",cases);
else printf("Scenario #%d:\nNo suspicious bugs found!\n\n",cases);
cases++;
}
//system("pause");
return 0;
}