1 #include<stdio.h> 2 #include<string.h> 3 int bug[2010],num[2010]; 4 int find(int x){ 5 int r=x; 6 while(r!=bug[r])r=bug[r]; 7 bug[x]=r; 8 return r; 9 } 10 void initial(){ 11 memset(bug,0,sizeof(bug)); 12 for(int i=1;i<=2000;i++)num[i]=1; 13 } 14 int merge(int x,int y){ 15 int f1,f2; 16 f1=find(x);f2=find(y); 17 if(f1!=f2)bug[f2]=f1,num[f1]+=num[f2]; 18 else return num[f1]; 19 return 0; 20 } 21 int main(){ 22 int T,N,M,a,b,flot,tot=0; 23 scanf("%d",&T); 24 while(T--){flot=1;tot++;initial(); 25 scanf("%d%d",&N,&M); 26 while(M--){ 27 scanf("%d%d",&a,&b); 28 if(!bug[a])bug[a]=a;if(!bug[b])bug[b]=b; 29 if(merge(a,b)&1)flot=0; 30 } 31 if(flot)printf("Scenario #%d: No suspicious bugs found! ",tot); 32 else printf("Scenario #%d: Suspicious bugs found! ",tot); 33 puts(""); 34 } 35 return 0; 36 }
思路错误,本想着只要环节点数是偶数就对的,仔细想想还是不对,网上搜的子节点与父节点关系推出当前关系,还有带权并查集不是很理解
//错的;;;