把单词的第一个字母和最后一个字母作为点，由第一个字母向最后一个字母连一条有向边, 问题转化为判断一个有向图是否存在欧拉道路 有向图存在欧拉道路的条件: 在忽略边的方向后,图必须是连通的,同时最多只能有两个点的入度不等于出度, 而且必须是其中一个点的出度刚好比入度大1(把它作为起点),另一个的入度比出度大1(把它作为终点).
代码：
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 const int N= 27; 6 int in[N], out[N],use[N], set[N]; 7 int find( int x) 8 { 9 int r=x; 10 if(r!= set[r]) 11 r= set[r]; 12 return r; 13 } 14 void merge( int x, int y) 15 { 16 int fx=find(x); 17 int fy=find(y); 18 if(fx!=fy) 19 { 20 set[fy]=fx; 21 } 22 } 23 int main() 24 { 25 int i,j,t,n,cnt1,cnt2,cnt3,flag; 26 char s[ 1001]; 27 scanf( " %d ",&t); 28 while(t--) 29 { 30 scanf( " %d ",&n); 31 memset( in, 0, sizeof( in)); 32 memset( out, 0, sizeof( out)); 33 memset(use, 0, sizeof(use)); 34 for(i= 0;i<= 26;i++) 35 set[i]=i; 36 while(n--) 37 { 38 scanf( " %s ",&s); 39 i=s[ 0]- ' a '; 40 j=s[strlen(s)- 1]- ' a '; 41 use[i]=use[j]= 1; 42 in[j]++; 43 out[i]++; 44 merge(i,j); 45 } 46 cnt1= 0,cnt2= 0,cnt3= 0; 47 flag= 1; 48 for(i= 0;i< 26;i++) 49 { 50 if(use[i]) 51 { 52 if( set[i]==i) 53 cnt1++; 54 if( in[i]!= out[i]) 55 { 56 if( in[i]- out[i]== 1) 57 cnt2++; 58 else if( out[i]- in[i]== 1) 59 cnt3++; 60 else 61 flag= 0; 62 } 63 } 64 } 65 if((cnt1== 1&&flag&&cnt2== 0&&cnt3== 0)||(cnt1== 1&&flag&&cnt2== 1&&cnt3== 1)) 66 puts( " Ordering is possible. "); 67 else 68 puts( " The door cannot be opened. "); 69 } 70 return 0; 71 }