此题不难，但因为一些细节酝酿了很久才写。最大的收获就是不同的构图角度会有截然不同的性能差异，如果把单词看作节点，那么问题将变成NP难的哈密顿回路，而如果抽象为边，将两个字母的连接抽象为对一个字母节点增加出边与入边，则瞬间变为判欧拉迹存在性的易解问题。
欧拉环游存在定理：原图的基图为连通图，且所有定点出入度相等。
欧拉路径存在定理：基图连通，除去出发点出度比入度多一，结束点入度比出度多一，其余点（如果有）出入度相等。
基图判连通：并查集
1
#include<cstdio>
2#include<cstdlib>
3#include<cstring>
4
5int degree[26][2];
6int set[26];
7bool hash[26];
8
9
int main()
{
10
int flag;
11 int inNum,outNum;
12 int _case,n,i,num;
13 char s,t,chr;
14 char tmp[1111];
15 scanf("%d",&_case);
16
while(_case--){
17 memset(degree,0,sizeof(degree));
18 memset(set,-1,sizeof(set));
19 memset(hash,0,sizeof(hash));
20 scanf("%d",&n); getchar();
21 for(i=0;i<n;i++){
22 gets(tmp);
23 s=tmp[0]; t=tmp[strlen(tmp)-1];
24 ++degree[s-'a'][0];
25 ++degree[t-'a'][1];
26 unino(s-'a',t-'a');
27 hash[s-'a']=hash[t-'a']=1;
28
}
29
30 for(num=i=0;i<26;i++) if(hash[i]) ++num;
31
32 for(flag=i=0;i<26;i++) if( set[i] == num*-1 ){ flag=true; break; }
33 /**//* 等价集应包含已出现的n个字母 */
34
35 if(!flag)
36 printf("The door cannot be opened.\n"); // 基图不联通
37 else{
38 flag=false;
39 for(inNum=outNum=i=0;i<26;i++)
40 if(degree[i][0]!=degree[i][1]){
41 if(degree[i][0]==degree[i][1]+1) ++inNum;
42 else
43 if(degree[i][1]==degree[i][0]+1) ++outNum;
44 else { flag=true; break; }
45 }
46 if(flag)
47 printf("The door cannot be opened.\n");
48 else
49 if( (inNum==1&outNum==1)|(inNum==0&outNum==0) )
50 printf("Ordering is possible.\n");
51 else
52 printf("The door cannot be opened.\n");
53 }
54 }
55 return 0;
56
}
57
58int find(int s){
59 if(set[s]<0) return s;
60 set[s]=find(set[s]);
61 return set[s];
62}
63
64void unino(int s,int t){
65 int root1,root2;
66 root1=find(s); root2=find(t);
67 if( root1 == root2 ) return ;
68 if(set[root1]<set[root2]){ set[root1]+=set[root2]; set[root2]=root1; }
69 else{ set[root2]+=set[root1]; set[root1]=root2; }
70}
71