此題不難，但因?yàn)橐恍┘?xì)節(jié)醞釀了很久才寫。最大的收獲就是不同的構(gòu)圖角度會有截然不同的性能差異，如果把單詞看作節(jié)點(diǎn)，那么問題將變成NP難的哈密頓回路，而如果抽象為邊，將兩個字母的連接抽象為對一個字母節(jié)點(diǎn)增加出邊與入邊，則瞬間變?yōu)榕袣W拉跡存在性的易解問題。
歐拉環(huán)游存在定理：原圖的基圖為連通圖，且所有定點(diǎn)出入度相等。
歐拉路徑存在定理：基圖連通，除去出發(fā)點(diǎn)出度比入度多一，結(jié)束點(diǎn)入度比出度多一，其余點(diǎn)（如果有）出入度相等。
基圖判連通：并查集
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 /**//* 等價集應(yīng)包含已出現(xiàn)的n個字母 */
34
35 if(!flag)
36 printf("The door cannot be opened.\n"); // 基圖不聯(liá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