HDU 1116 Play on Words這個題目要運用到歐拉路得相關(guān)知識，并且也要并查集，題目說的是：給你n個單詞，要你判斷這些單詞能不能首尾相連。
理解題目意思后，進(jìn)行轉(zhuǎn)化，輸入字符串，提取首位字母作為下標(biāo)來表示兩節(jié)點的出現(xiàn)，以及相對應(yīng)節(jié)點入度和出度的增加，
轉(zhuǎn)化為并查集的應(yīng)用即可。那么從可以想象一幅由首位字母節(jié)點構(gòu)成的圖，當(dāng)且僅當(dāng)圖是一條歐拉回路或者歐拉通路的時候，
才能滿足題目的要求，至于歐拉回路和歐拉通路的判定可以總結(jié)為如下：
1）所有的點聯(lián)通
2）歐拉回路中所有點的入度和出度一樣。
3）歐拉通路中起點的入度 - 出度 = 1，終點的 初度 - 入度 = 1， 其他的所有點入度 = 出度；
有了上面這些知識點做鋪墊，相信理解起來就比較容易了，下面我的代碼：
1 #include<stdio.h>
2 #include<string.h>
3 #include<math.h>
4 #define N 30
5 /*
6 歐拉回路，所有點連通，并且所有點的入度等于出度。
7 歐拉通路。從原點 S出發(fā)，經(jīng)過所有點，從終點 t出去。
8 所有點除起點終點外的度都是偶數(shù)，且出度等于入度
9 起點的出度比入度大 1
10 終點的入度比出度大 1
11 */
12
13 int father[N],vis[N];
14 //father[i] 表示節(jié)點 i 的 BOSS ！ vis[i]表示節(jié)點 i 出現(xiàn)過！
15 int findx(int x)
16 { //找節(jié)點 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é)點 a 和節(jié)點 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é)點 a 和 b的入度和出度
49 vis[a]=1;
50 vis[b]=1; //標(biāo)記節(jié)點 a 和 b的出現(xiàn)
51 }
52 for(i=0;i<26;i++)
53 father[i]=findx(i); //找出每個節(jié)點的 BOSS
54 for(cnt=0,i=0;i<26;i++)
55 if(vis[i] && father[i]==i)
56 cnt++; // 統(tǒng)計最終 BOSS 即根節(jié)點的個數(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)計入度和出度不相等的點的信息
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