拉姆剛開始學(xué)習(xí)英文單詞说敏，對單詞排序很感興趣鸥跟。如果給拉姆一組單詞，他能夠迅速確定是否可以將這些單詞排列在一個列表中盔沫，使得該列表中任何單詞的首字母與前一單詞的尾字母相同医咨。你能編寫一個程序來幫助拉姆進(jìn)行判斷嗎？

輸入描述：
輸入包含多組測試數(shù)據(jù)架诞。對于每組測試數(shù)據(jù)拟淮，第一行為一個正整數(shù)n，代表有n個單詞谴忧。然后有n個字符串很泊，代表n個單詞。保證：2<=n<=200沾谓，每個單詞長度大于1且小于等于10委造，且所有單詞都是由小寫字母組成。
輸出描述：
對于每組數(shù)據(jù)均驶，輸出"Yes"或"No"

輸入例子1:
3
abc
cdefg
ghijkl
輸出例子1：
Yes

輸入例子2：
4
abc
cdef
fghijk
xyz
輸出例子2：
No

由題意可知昏兆，對于輸入單詞的順序我們是可以調(diào)整的，也就是說無論怎么調(diào)整單詞的順序妇穴，只要能形成接龍即可爬虱。

可能有人會想到通過調(diào)整單詞的順序，比如按首字母或尾字母對輸入的單詞進(jìn)行重新排序再依次檢查首尾是否可以形成接龍腾它，這樣就掉入了本題的第一個陷阱跑筝。事實(shí)上，在本題中26個英文字母是沒有所謂的先后順序的携狭，因?yàn)槲覀円袛嗟氖沁@些單詞能否形成一條接龍继蜡，即使你的首字母是a而我的首字母是z，但是你的單詞是abc中而我的是單詞zxa逛腿，你的單詞仍然排在我的后面稀并。

這里有人可能已經(jīng)看出來了，如果把每個單詞看成一條有向邊单默，首尾字母看成邊上的起點(diǎn)和終點(diǎn)碘举，問題就轉(zhuǎn)化成了判斷一個有向圖是否可以表示為一條（不閉合的）歐拉路徑或歐拉回路的一筆畫問題。

根據(jù)有向圖中歐拉路徑的判定定理
　　一個連通的有向圖可以表示為一條從起點(diǎn)到終點(diǎn)的（不閉合的）歐拉路徑的充要條件是： 起點(diǎn)的出度比入度多1搁廓， 終點(diǎn)的入度比出度多1引颈，而其它頂點(diǎn)的入度和出度都相等耕皮。
　　一個連通的有向圖可以表示為一條歐拉回路的充要條件是：每個頂點(diǎn)的入度和出度都相等

注意到上面我對連通的三個字進(jìn)行了加粗，目的是強(qiáng)調(diào)不要忘記判斷有向圖的連通性（這里只要滿足弱連通即可）蝙场，對于百度那道筆試題網(wǎng)上很多人只考慮到統(tǒng)計點(diǎn)的入度與出度來判斷是否能形成接龍凌停，而沒有檢驗(yàn)有向圖的連通性，雖然這樣的代碼能通過攀勐耍客OJ上所有的測試用例罚拟，但實(shí)際上對于aba，cdc完箩，efe這樣的輸入?yún)s會得到錯誤的輸出"Yes"赐俗，原因就是這些單詞形成的有向圖是不連通的。這也從側(cè)面說明了疟字客OJ上用例設(shè)計的不夠全面阻逮。
源碼如下：

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main 
{

    public static void main(String[] args) 
    {
        // TODO Auto-generated method stub
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext())
        {
            int n = scan.nextInt();
            String[] arr = new String[n];
            for(int i = 0; i < n ; i++)
                arr[i] = scan.next();
            System.out.println(WordListOrder.canArrangeWords(n, arr));
        }
        scan.close();
    }

}

class WordListOrder {

    public static String canArrangeWords(int n, String[] arr)
    {
        // 26個英文字母看作26個點(diǎn),用整數(shù)0-25來表示
        int[][] directedGraph = new int [26][26];// 鄰接矩陣表示有向圖
        int[] inDegree = new int [26];           // 頂點(diǎn)入度
        int[] outDegree = new int [26];          // 頂點(diǎn)出度
        boolean[] hasLetter = new boolean[26];   // 標(biāo)記字母是否出現(xiàn)過
        boolean hasEuler = false;                 // 有狹義歐拉路徑或歐拉回路標(biāo)志
        for(int i = 0; i < n; i++)
        {
            String word = arr[i];
            char firstLetter = word.charAt(0);
            char lastLetter = word.charAt(word.length()-1);
            outDegree[firstLetter - 'a']++;
            inDegree[lastLetter - 'a']++;
            directedGraph[firstLetter - 'a'][lastLetter - 'a'] = 1; // 有向圖
            hasLetter[firstLetter - 'a'] = true;
            hasLetter[lastLetter - 'a'] = true;
        }
        int startNum = 0;        
        int endNum = 0;
        for (int vertex = 0; vertex < 26; vertex++)
        {
            if(outDegree[vertex] - inDegree[vertex] == 1)    // 起點(diǎn)
                startNum++;                    
            if(inDegree[vertex] - outDegree[vertex] == 1)    // 終點(diǎn)
                endNum++;
            if(Math.abs(inDegree[vertex] - outDegree[vertex]) > 1)
            {
                hasEuler = false;
                break;
            }
        }
        boolean isEulerPath = (startNum == 1 && endNum == 1);   // 這里指狹義上的歐拉路徑，不包括歐拉回路
        boolean isEulerCircuit = (startNum == 0 && endNum == 0);// 歐拉回路
        if((!isEulerPath) && (!isEulerCircuit))    // 既不是歐拉路徑也不是歐拉回路
            hasEuler = false;
        // 判斷是否弱連通
        int vertexNum = 0;    // 統(tǒng)計圖中點(diǎn)的個數(shù)
        for(int letter = 0; letter < 26; letter++)
        {
            if(hasLetter[letter])    
                vertexNum++;
        }
        int firstWordFirstLetter = arr[0].charAt(0) - 'a';// 以第一個單詞的首字母作為起點(diǎn)進(jìn)行BFS
        hasEuler = hasEuler && isConnected(firstWordFirstLetter, vertexNum, directedGraph);
        if(hasEuler)
            return "Yes";
        else
            return "No";
    }

    // 判斷有向圖是否弱連通秩彤，即轉(zhuǎn)換成無向圖判斷是否連通
    public static boolean isConnected(int start, int vertexNum, int[][] directedGraph)
    {
        int[][] undirectedGraph = new int[26][26];
        for(int i = 0; i < 26; i++)     // 把有向圖轉(zhuǎn)換成無向圖
        {
            for(int j = 0; j < 26; j++) 
            {
                if(directedGraph[i][j] == 1)
                {
                    undirectedGraph[i][j] = 1;
                    undirectedGraph[j][i] = 1;
                }
            }
        }
        Queue<Integer> queue = new LinkedList<Integer>();
        boolean[] passedVertex = new boolean[26];
        int passedVertexNum = 0;
        queue.offer(start);
        // 從起點(diǎn)開始進(jìn)行BFS叔扼，統(tǒng)計遍歷到點(diǎn)的個數(shù)
        while(!queue.isEmpty())
        {
            int currentVertex = queue.poll();
            passedVertex[currentVertex] = true;
            passedVertexNum++;
            for(int vertex = 0; vertex < 26; vertex++)
            {
                if(undirectedGraph[currentVertex][vertex] == 1 && passedVertex[vertex] == false)
                    queue.offer(vertex);
            }
        }
        // 遍歷到所有的點(diǎn)，證明無向圖是連通的
        if(passedVertexNum == vertexNum)
            return true;
        else 
            return false;
    }
}