这题也是并查集的高级应用。
我就不多讲了，做这题之前，我建议把食物链好好搞懂，那么这题就自然而然会了，食物链有三种性别，而这里只有两种关系，更加简单，所以食物链一定要搞懂。
#include<iostream> using namespace std; #define N 2005 int p[N],r[N]; void init(int n) { for(int i=1;i<=n;i++) { p[i]=i; r[i]=0; } } int find(int x) { if(p[x]==x) return x; int temp=p[x]; p[x]=find(p[x]); r[x]=(r[temp]+r[x])%2; return p[x]; } void merge(int x,int y,int rx,int ry) { p[ry]=rx; r[ry]=(r[x]+r[y]+1)%2; } int main() { int n,k,x,y,xx,yy,ca; bool flag; scanf("%d",&ca); for(int i=1;i<=ca;i++) { flag=true; scanf("%d%d",&n,&k); init(n); while(k--) { scanf("%d%d",&x,&y); if(!flag) continue; xx=find(x),yy=find(y); if(xx==yy) { if(r[x]==r[y]) flag=false; } else merge(x,y,xx,yy); } printf("Scenario #%d:/n",i); if(flag) printf("No suspicious bugs found!/n/n"); else printf("Suspicious bugs found!/n/n"); } return 0; }
