[UVA] 10129 - Play on Words

題意:
輸入多個字串，
問是否可以以某一種排列方式，
使得第一個字串的尾與第二個字串的頭相同，
第二個字串的尾與第三個字串的頭相同，
第N個字串的尾與第N+1個字串的頭相同，
如果可以輸出"Ordering is possible."
不行則輸出"The door cannot be opened."

--------------------------------------------------

方法:
如果將每個字串的頭尾都假設為一個節點，
那麼就會形成一個有向圖，
例如apple，可以變成節點 a 連向節點 e ，
那麼這題所求的就是有沒有存在尤拉路徑(或迴路)。

判斷是否有尤拉路徑或迴路必須滿足三點:
1.將有向邊都看成無向邊的話，此圖必須連通。
2.尤拉路徑只能有一個起點一個終點，
   起點(入度=出度+1)，終點(出度=入度+1)，
   除了起點終點以外，所有節點出度都等於入度，
   若該節點出度不等於入度且不滿足起點或終點的條件則尤拉路徑不存在。
3.若所有節點出度都等於入度，表示不存在起點和終點=>存在尤拉迴路。


而判斷是否連通的方法可以用DFS或disjoint set，
這裡我使用disjoint set 判斷。
--------------------------------------------------
/* 20150822
 * hanting
 * UVa 10129 - Play on Words
 * C++
 */
#include <iostream>
using namespace std;
int parent[26];
void initial()
{
    for(int i=0;i<26;i++)
    {
        parent[i]=-1;
    }
}
int Find(int x)
{
    if(parent[x]<0) return x;
    else
    {
        return parent[x]=Find(parent[x]);
    }
}
void Union(int x,int y)
{
    int Fx=Find(x);
    int Fy=Find(y);
    if(Fx!=Fy)
    {
        if(parent[Fx]<parent[Fy])
        {
            parent[Fx]+=parent[Fy];
            parent[Fy]=Fx;
        }
        else
        {
            parent[Fy]+=parent[Fx];
            parent[Fx]=Fy;
        }
    }
    else
        parent[Fx]--;
}
int main()
{
    int caseN;
    cin>>caseN;
    while(caseN--)
    {
        int wordN;
        cin>>wordN;
        string word[wordN];
        initial();
        int table[26][26]={};
        for(int i=0;i<wordN;i++)
        {
            cin>>word[i];
            int head=word[i][0]-'a';
            int last=word[i][word[i].size()-1]-'a';
            table[head][last]++;//head connect last
            Union(head,last);
        }


        int cnt=0;
        for(int i=0;i<26;i++)
        {
            if(parent[i]<-1) cnt++;
        }

        bool connected=(cnt==1);//是否為連通圖

        int start=0,End=0;
        bool possible=true;
        for(int i=0;i<26 and connected;i++)
        {
            int indegree=0;
            int outdegree=0;
            for(int j=0;j<26;j++)
            {
                outdegree+=table[i][j];
                indegree+=table[j][i];
            }
            if(indegree!=outdegree)
            {
                if(indegree==outdegree+1)
                    start++;
                else if(indegree+1==outdegree)
                    End++;
                else
                    possible=false;
            }
        }
        possible&=((start==1 and End==1)or(start==0 and End==0));
        if(connected and possible)
        {
            cout<<"Ordering is possible."<<endl;
        }
        else
        {
            cout<<"The door cannot be opened."<<endl;
        }
    }
    return 0;
}
--------------------------------------------------
範例輸入:
input.txt

範例輸出:
output.txt

--------------------------------------------------