考虑状态压缩中,关系就是叠加。
一直wa,wa在Find以后是判断各自的关系。#includeusing namespace std;const int N=2e3+10;int pre[N],n,sum[N],m;bool flag;int Find(int x){ if(pre[x]==x) return x; int temp=pre[x]; pre[x]=Find(temp); sum[x]=(sum[x]+sum[temp])%2; return pre[x];}void Merge(int x,int y){ int xx=Find(x); int yy=Find(y); if(xx==yy) { if(sum[x]==sum[y]) flag=false; } else{ pre[xx]=yy; sum[xx]=(sum[y]+sum[x]+1)%2; //父子之间不是同性恋; }}int main(){ int T,cas=1; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i=0;i<=n;i++) { pre[i]=i; sum[i]=0; } flag=true; while(m--) { int x,y; scanf("%d%d",&x,&y); if(!flag) continue; Merge(x,y); } printf("Scenario #%d:\n",cas++); if(flag) puts("No suspicious bugs found!"); else puts("Suspicious bugs found!"); puts(""); } return 0;}