题目链接:
AC代码:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #include<vector> 5 #include<algorithm> 6 #include<queue> 7 using namespace std; 8 typedef long long ll; 9 10 const int N=30; 11 bool book[N]; 12 int f[N],in[N],out[N]; 13 char s[1100]; 14 15 int getf(int x) 16 { 17 if(f[x]==x) 18 return x; 19 return f[x]=getf(f[x]); 20 } 21 22 void merge(int x,int y) 23 { 24 int t1=getf(x); 25 int t2=getf(y); 26 f[t2]=t1; 27 } 28 29 void init() 30 { 31 memset(book,0,sizeof(book)); 32 memset(in,0,sizeof(in)); 33 memset(out,0,sizeof(out));//in、out一定记得清空 34 for(int i=0; i<26; i++) 35 f[i]=i; 36 } 37 38 int main() 39 { 40 int t,n; 41 scanf("%d",&t); 42 while(t--) 43 { 44 init(); 45 scanf("%d",&n); 46 for(int i=1; i<=n; i++) 47 { 48 scanf("%s",s); 49 int len=strlen(s); 50 int x=s[0]-'a',y=s[len-1]-'a'; 51 merge(x,y); 52 in[y]++,out[x]++; 53 book[x]=1,book[y]=1; 54 } 55 int w=0,x=0,y=0,z=0; 56 for(int i=0; i<26; i++) 57 { 58 if(book[i]&&f[i]==i) 59 w++; 60 } 61 if(w>=2) 62 printf("The door cannot be opened.\n"); 63 else 64 { 65 for(int i=0; i<26; i++) 66 { 67 if(book[i]) 68 { 69 if(in[i]!=out[i]) 70 x++; 71 if(in[i]-out[i]==1) 72 y++; 73 if(out[i]-in[i]==1) 74 z++; 75 } 76 } 77 if(x==0) 78 printf("Ordering is possible.\n"); 79 else if(x==2&&y==1&&y==z) 80 printf("Ordering is possible.\n"); 81 else 82 printf("The door cannot be opened.\n"); 83 } 84 } 85 return 0; 86 }