#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn=2000+100; int fa[maxn]; int relate[maxn];//记录与父节点的性别关系,1代表异性,0代表同性 int n,m; int kase=0; int root(int x) { if(x==fa[x]) return x; int t=root(fa[x]); relate[x]=(relate[x]+relate[fa[x]])%2; fa[x]=t; return fa[x]; } void merge(int x,int y) { int fx=root(x); int fy=root(y); if(fx==fy) return; fa[fx]=fy; relate[fx]=(relate[y]+relate[x]+1)%2; return; } int main() { int T; int a,b; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) fa[i]=i,relate[i]=0; bool flag=false; for(int j=1;j<=m;j++) { scanf("%d%d",&a,&b); if(root(a)==root(b)&&relate[a]==relate[b]) { flag=true; } else merge(a,b); //printf("yes\n"); } //printf("dsasd\n"); printf("Scenario #%d:\n",++kase); if(flag) printf("Suspicious bugs found!\n\n"); else printf("No suspicious bugs found!\n\n"); } return 0; }
原文:http://www.cnblogs.com/xuejianye/p/5701215.html