HDU 1116 Play on Words這個(gè)題目要運(yùn)用到歐拉路得相關(guān)知識(shí)，并且也要并查集，題目說(shuō)的是：給你n個(gè)單詞，要你判斷這些單詞能不能首尾相連。
理解題目意思后，進(jìn)行轉(zhuǎn)化，輸入字符串，提取首位字母作為下標(biāo)來(lái)表示兩節(jié)點(diǎn)的出現(xiàn)，以及相對(duì)應(yīng)節(jié)點(diǎn)入度和出度的增加，
轉(zhuǎn)化為并查集的應(yīng)用即可。那么從可以想象一幅由首位字母節(jié)點(diǎn)構(gòu)成的圖，當(dāng)且僅當(dāng)圖是一條歐拉回路或者歐拉通路的時(shí)候，
才能滿(mǎn)足題目的要求，至于歐拉回路和歐拉通路的判定可以總結(jié)為如下：
1）所有的點(diǎn)聯(lián)通
2）歐拉回路中所有點(diǎn)的入度和出度一樣。
3）歐拉通路中起點(diǎn)的入度 - 出度 = 1，終點(diǎn)的 初度 - 入度 = 1， 其他的所有點(diǎn)入度 = 出度；
有了上面這些知識(shí)點(diǎn)做鋪墊，相信理解起來(lái)就比較容易了，下面我的代碼：
1 #include<stdio.h>
2 #include<string.h>
3 #include<math.h>
4 #define N 30
5 /*
6 歐拉回路，所有點(diǎn)連通，并且所有點(diǎn)的入度等于出度。
7 歐拉通路。從原點(diǎn) S出發(fā)，經(jīng)過(guò)所有點(diǎn)，從終點(diǎn) t出去。
8 所有點(diǎn)除起點(diǎn)終點(diǎn)外的度都是偶數(shù)，且出度等于入度
9 起點(diǎn)的出度比入度大 1
10 終點(diǎn)的入度比出度大 1
11 */
12
13 int father[N],vis[N];
14 //father[i] 表示節(jié)點(diǎn) i 的 BOSS ！ vis[i]表示節(jié)點(diǎn) i 出現(xiàn)過(guò)！
15 int findx(int x)
16 { //找節(jié)點(diǎn) x 的 BOSS ！
17 if(father[x]!=x)
18 father[x]=findx(father[x]);
19 return father[x];
20 }
21 void merge(int a,int b)
22 { // 合并 節(jié)點(diǎn) a 和節(jié)點(diǎn) b ！
23 int x,y;
24 x=findx(a);
25 y=findx(b);
26 if(x!=y) father[x]=y;
27 }
28 int main()
29 {
30 int text,cnt,i,j,n,out[N],in[N],p[30],a,b;
31 char str[1001];
32 scanf("%d",&text);
33 while(text--)
34 {
35 scanf("%d",&n);
36 memset(out,0,sizeof(out));
37 memset(in,0,sizeof(in));
38 memset(vis,0,sizeof(vis));
39 for(i=0;i<26;i++)
40 father[i]=i; //初始化數(shù)組
41 while(n--)
42 { // 處理所給信息 ！
43 scanf("%s",str);
44 a=str[0]-'a';
45 b=str[strlen(str)-1]-'a';
46 merge(a,b);
47 out[a]++;
48 in[b]++; // 記錄節(jié)點(diǎn) a 和 b的入度和出度
49 vis[a]=1;
50 vis[b]=1; //標(biāo)記節(jié)點(diǎn) a 和 b的出現(xiàn)
51 }
52 for(i=0;i<26;i++)
53 father[i]=findx(i); //找出每個(gè)節(jié)點(diǎn)的 BOSS
54 for(cnt=0,i=0;i<26;i++)
55 if(vis[i] && father[i]==i)
56 cnt++; // 統(tǒng)計(jì)最終 BOSS 即根節(jié)點(diǎn)的個(gè)數(shù) 。
57 if(cnt>1) //圖不連通
58 {
59 printf("The door cannot be opened.\n");
60 continue;
61 }
62
63 for(j=0,i=0;i<26;i++)
64 if(vis[i] && out[i]!=in[i])
65 p[j++]=i; //統(tǒng)計(jì)入度和出度不相等的點(diǎn)的信息
66 if(j==0)
67 {//歐拉回路，即環(huán)
68 printf("Ordering is possible.\n");
69 continue;
70 }
71 if(j==2 && ( out[p[0]]-in[p[0]]==1 && in[p[1]]-out[p[1]]==1
72 || out[p[1]]-in[p[1]]==1 && in[p[0]]-out[p[0]]==1 ) )
73 {//歐拉通路
74 printf("Ordering is possible.\n");
75 continue;
76 }
77 printf("The door cannot be opened.\n");
78 }
79 return 0;
80 }
81