题意：

n只虫子 m种交配方式 并给出m对交配 问 是否存在基… 0.0

思路：

简单的带权并查集 比POJ上那道食物链基础 而且用二分染色可以水过（由于性别只有两种…）

带权并查集可以利用权值维护不同集合间的“关系”

代码书写时注意getf函数中利用fa[x]更新x和根的关系 merge时注意fy权值利用x、y的权值的计算方法

代码：

#include
  
   
#include
   
     #include
    
      using namespace std; #define N 2010 int fa[N],val[N]; int n,m,T,t; int getf(int x) { if(x!=fa[x]) { int tmp=fa[x]; fa[x]=getf(fa[x]); val[x]=(val[x]+val[tmp])%2; } return fa[x]; } int main() { int i,u,v,flag,fu,fv; scanf("%d",&T); for(t=1;t<=T;t++) { scanf("%d%d",&n,&m); for(i=1;i<=n;i++) { fa[i]=i; val[i]=0; } for(i=1,flag=1;i<=m;i++) { scanf("%d%d",&u,&v); fu=getf(u); fv=getf(v); if(fu==fv) { if(val[u]==val[v]) flag=0; } else { fa[fv]=fu; val[fv]=(val[u]+val[v]+1)%2; } } printf("Scenario #%d:\n",t); if(flag) printf("No suspicious bugs found!\n"); else printf("Suspicious bugs found!\n"); puts(""); } return 0; }