原題鏈接：?[http://acm.hdu.edu.cn/showproblem.php?pid=1116](http://acm.hdu.edu.cn/showproblem.php?pid=1116)
**一：原題內容**
Problem Description
Some of the secret doors contain a very interesting word puzzle. The team of archaeologists has to solve it to open that doors. Because there is no other way to open the doors, the puzzle is very important for us.?
There is a large number of magnetic plates on every door. Every plate has one word written on it. The plates must be arranged into a sequence in such a way that every word begins with the same letter as the previous word ends. For example, the word acm can be followed by the word motorola. Your task is to write a computer program that will read the list of words and determine whether it is possible to arrange all of the plates in a sequence (according to the given rule) and consequently to open the door.?
Input
The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing a single integer number Nthat indicates the number of plates (1 <= N <= 100000). Then exactly Nlines follow, each containing a single word. Each word contains at least two and at most 1000 lowercase characters, that means only letters 'a' through 'z' will appear in the word. The same word may appear several times in the list.?
Output
Your program has to determine whether it is possible to arrange all the plates in a sequence such that the first letter of each word is equal to the last letter of the previous word. All the plates from the list must be used, each exactly once. The words mentioned several times must be used that number of times.?
If there exists such an ordering of plates, your program should print the sentence "Ordering is possible.". Otherwise, output the sentence "The door cannot be opened.".?
Sample Input
~~~
3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok
~~~
Sample Output
~~~
The door cannot be opened.
Ordering is possible.
The door cannot be opened.
~~~
**二：分析理解**
題目大意：給你一些英文單詞，判斷所有單詞能不能連成一串，類似成語接龍的意思。但是如果有多個重復的單詞時，也必須滿足這樣的條件才能算YES。否則都是不可能的情況。
解題思路：歐拉路的基本題。只要知道就可以做出來了。
關于歐拉回路和歐拉路徑
定義：
歐拉回路：每條邊恰好只走一次，并能回到出發點的路徑
歐拉路徑：經過每一條邊一次，但是不要求回到起始點
①首先看歐拉回路存在性的判定：
一、無向圖
每個頂點的度數都是偶數，則存在歐拉回路。
二、有向圖（所有邊都是單向的）
每個節頂點的入度都等于出度，則存在歐拉回路。
?三.混合圖歐拉回路
混合圖歐拉回路用的是網絡流。
把該圖的無向邊隨便定向，計算每個點的入度和出度。如果有某個點出入度之差為奇數，那么肯定不存在歐拉回路。因為歐拉回路要求每點入度 = 出度，也就是總度數為偶數，存在奇數度點必不能有歐拉回路。
好了，現在每個點入度和出度之差均為偶數。那么將這個偶數除以2，得x。也就是說，對于每一個點，只要將x條邊改變方向（入>出就是變入，出>入就是變出），就能保證出 = 入。如果每個點都是出 = 入，那么很明顯，該圖就存在歐拉回路。
現在的問題就變成了：我該改變哪些邊，可以讓每個點出 = 入？構造網絡流模型。首先，有向邊是不能改變方向的，要之無用，刪。一開始不是把無向邊定向了嗎？定的是什么向，就把網絡構建成什么樣，邊長容量上限1。另新建s和t。對于入 > 出的點u，連接邊(u, t)、容量為x，對于出 > 入的點v，連接邊(s, v)，容量為x（注意對不同的點x不同）。之后，察看是否有滿流的分配。有就是能有歐拉回路，沒有就是沒有。歐拉回路是哪個？查看流值分配，將所有流量非 0（上限是1，流值不是0就是1）的邊反向，就能得到每點入度 =
出度的歐拉圖。
由于是滿流，所以每個入 > 出的點，都有x條邊進來，將這些進來的邊反向，OK，入 = 出了。對于出 > 入的點亦然。那么，沒和s、t連接的點怎么辦？和s連接的條件是出 > 入，和t連接的條件是入 > 出，那么這個既沒和s也沒和t連接的點，自然早在開始就已經滿足入 = 出了。那么在網絡流過程中，這些點屬于“中間點”。我們知道中間點流量不允許有累積的，這樣，進去多少就出來多少，反向之后，自然仍保持平衡。
所以，就這樣，混合圖歐拉回路問題，解了。
②.歐拉路徑存在性的判定
一。無向圖
一個無向圖存在歐拉路徑，當且僅當 ? 該圖所有頂點的度數為偶數 ? 或者 ?除了兩個度數為奇數外其余的全是偶數。
二。有向圖
一個有向圖存在歐拉路徑，當且僅當 該圖所有頂點的度數為零 ? ? 或者 一個頂點的度數為1，另一個度數為-1，其他頂點的度數為0。
三。混合圖歐拉路徑
其實整篇文章只有這部分是我寫的哈，灰常不好意思，只是網上的同志們寫的太好了，實在沒有必要重復勞動，不知道大家有沒有發現，求歐拉路徑的第一步一定是求歐拉回路，在混合圖上也不例外，如何判斷混合圖歐拉回路問題的存在性呢？首先，我們用上文所說的方法判斷該圖是否存在歐拉回路，如果存在，歐拉路徑一定存在。如果歐拉回路不存在，那么我們枚舉歐拉路徑的起點和終點，連接一條無向邊，然后再用最大流判斷是否存在歐拉回路即可。
所以這道題的大題思路就是：
1.并查集判斷連通
2.將每個單詞取出首字母和尾字母，轉換為一條邊，然后加入對應的連通分量中。如果這個字母出現過，visit數組標記為true。同時起點出度加1，終點入度加1.
3.判斷一下：
1）這個圖必須是連通的，即根結點只有一個。如果不是，直接結束本次算法。
2）如果這個圖是連通的，判斷每個結點的入度和出度情況。
如果這個圖是歐拉路，則每個頂點的出度等于入度。即out[i] = in[i]
如果這個圖是半歐拉圖，則起點的出度比入度大1，終點的入度比出度大1.其余頂點的出度等于入度。
如果滿足上述條件，就可以將所有單詞鏈接起來，否則不能。
當然，在判斷出度入度的時候還有一點需要注意，那就是除了起點終點以外的頂點，出度必須等于入度（出度入度可以同時為2，即環），但是起點和終點必須保證出度和入度之差為1。
**三：AC代碼**
~~~
#define _CRT_SECURE_NO_DEPRECATE
#define _CRT_SECURE_CPP_OVERLOAD_STANDARD_NAMES 1
#include<iostream>
#include<string.h>
using namespace std;
char ch[1001]; //存儲單詞
int pre[27]; //一共26個英文字母，下標從1開始，用于并查集
int in[27]; //表示每個單詞的尾部字母的入度，默認是0
int out[27]; //表示每個單詞的頭部字母的出度，默認是0
bool visited[27]; //字母是否出現，默認是false
int T; //測試實例個數
int N; //每個實例要輸入的單詞的個數
int inNum; //判斷出現的所有的字母,“入度減出度為1”的個數
int outNum; //判斷出現的所有的字母,“出度減入度為1”的個數
int root; //根節點個數
bool flag; //判斷出現的所有的字母的出度和入度之差是否是0或1，如果不是，那肯定不滿足題意,還有判斷root是否大于1，大于1的話，肯定不滿足
int start;
int last;
int Find(int x)
{
return (x != pre[x]) ? Find(pre[x]) : x;
}
void Union(int x, int y)
{
int root_x = Find(x);
int root_y = Find(y);
if (root_x != root_y)
pre[root_x] = root_y;
}
int main()
{
cin >> T;
while (T--)
{
for (int i = 1; i < 27; i++)
pre[i] = i;
memset(in, 0, sizeof(in));
memset(out, 0, sizeof(out));
memset(visited, 0, sizeof(visited));
inNum = outNum = root = 0;
flag = true;
cin >> N;
for (int i = 0; i < N; i++)
{
cin >> ch;
int len = strlen(ch);
start = ch[0] - 'a' + 1;
last = ch[len - 1] - 'a' + 1;
visited[start] = true;
visited[last] = true;
out[start]++;
in[last]++;
Union(start, last);
}
for (int i = 1; i <= 26; i++)
{
if (visited[i])
{
if (pre[i] == i)
root++;
if (out[i] != in[i])//注意點
{
if (out[i] - in[i] == 1)
outNum++;
else if (in[i] - out[i] == 1)
inNum++;
else
flag = false;
}
}
if (!flag)
break;
if (root > 1)
{
flag = false;
break;
}
}
if ((flag&&inNum == 0 && outNum == 0) || (flag&&inNum == 1 && outNum == 1))
cout << "Ordering is possible.\n";
else
cout << "The door cannot be opened.\n";
}
return 0;
}
~~~
參考 ：[http://www.acmerblog.com/hdu-1116-play-on-words-1412.html](http://www.acmerblog.com/hdu-1116-play-on-words-1412.html)
