并查集，欧拉回路
View Code
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 int n,len1; 5 char s[1005]; 6 int a[30],b[30]; 7 int set[30]; 8 int find(int x) 9 { 10 if(x!=set[x]) 11 set[x]=find(set[x]); 12 return set[x]; 13 } 14 void met() 15 { 16 int i,x,y; 17 for(i=1;i<=n;i++) 18 { 19 20 scanf("%s",s); 21 len1=strlen(s); 22 x=s[0]-'a'+1; 23 y=s[len1-1]-'a'+1; 24 a[y]++; 25 b[x]++; 26 int f1=find(y); 27 int f2=find(x); 28 if(f1!=f2) 29 set[f1]=f2; 30 } 31 } 32 33 int main() 34 { 35 int t,i,f1,f2,f3; 36 scanf("%d",&t); 37 while(t--) 38 { 39 scanf("%d",&n); 40 memset(a,0,sizeof(a)); 41 memset(b,0,sizeof(b)); 42 for(i=1;i<=26;i++) 43 set[i]=i; 44 met(); 45 int c=0; 46 for(i=1;i<=26;i++) 47 { 48 if(set[i]==i&&a[i]&&b[i]) 49 c++; 50 } 51 if(c>1) 52 { 53 printf("The door cannot be opened.\n"); 54 continue; 55 } 56 f1=f2=f3=0; 57 for(i=1;i<=26;i++) 58 { 59 if(a[i]-b[i]==1)f1++; 60 if(a[i]-b[i]==-1)f2++; 61 if(a[i]-b[i]==0)f3++; 62 } 63 if(f1==1&&f1==f2&&f1+f2+f3==26) 64 printf("Ordering is possible.\n"); 65 else if(f1==0&&f2==0&&f3==26) 66 printf("Ordering is possible.\n"); 67 else 68 printf("The door cannot be opened.\n"); 69 } 70 return 0; 71 }