hdu1829 A Bug's Life(並查集)
開兩個並查集，然後合並的時候要合並兩次，這樣在合並之前判斷是否沖突，如果不沖突就進行合並，否則不需要繼續合並。
#include
#include
#include
#include
using namespace std;
const int MAX=2000;
int pre[2*MAX+5];
bool mark;
void init(int n){
int i;
for(i=1;i<=MAX+n;i++) pre[i]=i;
mark=true;
}
int root(int x){
if(x!=pre[x]){
pre[x]=root(pre[x]);
}
return pre[x];
}
void merge(int x,int y){
int fx,fy;
fx=root(x);
fy=root(y-MAX);
if(fx==fy) {
mark=false;
return;
}
fy=root(y);
if(fx!=fy){
pre[fx]=pre[fy];
}
}
int main()
{
int t,i,n,m,x,y,k;
scanf("%d",&t);
for(i=1;i<=t;i++){
scanf("%d%d",&n,&m);
init(n);
for(k=1;k<=m;k++){
scanf("%d%d",&x,&y);
if(mark){
merge(x,y+MAX);
merge(y,x+MAX);
}
}
printf("Scenario #%d:\n",i);
if(mark){
printf("No suspicious bugs found!\n");
}else{
printf("Suspicious bugs found!\n");
}
printf("\n");
}
return 0;
}
