題目大意

這個題讓我們求給出的幾個字符串是否能全部首尾相連义屏，字符串長度至少為2，其連接方式類似于成語接龍蜂大，需要一個字符串的尾巴與第二個字符串開頭相同闽铐。

樣例輸入

3
2
acm
ibm
3
acm
malform
mouse
2
ok
ok

樣例輸出

The door cannot be opened.
Ordering is possible.
The door cannot be opened.

題目分析

這題是個歐拉回路和并查集的結(jié)合。因為我是菜鳥還不是很懂歐拉回路就不在此贅述奶浦，日后理解后再詳細寫兄墅。
先說說我的想法：
1.將每個輸入的字符串的首字母與尾字母的入度和出度分別加一，分別放在in[]與out[]數(shù)組中澳叉。并記錄出現(xiàn)過的字母（只記錄首位）隙咸。

2.判定其是否滿足題目所給的條件相連即只有一個字母入度減出度為1，一個字母入度減出度為-1成洗，剩下的入度減去出度都為0五督。若不滿足直接退出。

3.剩下的就判斷其是否有連通性瓶殃，我使用并查集的時候?qū)ather數(shù)組的根節(jié)點位置記錄為他節(jié)點的個數(shù)并以負數(shù)表示充包。然后每輸入一個字符串將首尾字母合并，而若是首尾字母相同遥椿，則不合并基矮。這樣若形成的是鏈而不是環(huán)的話，father數(shù)組中最小的值（因為是負數(shù)）就與輸入的字符串首尾字母出現(xiàn)的個數(shù)相同冠场。
若相同則判斷可行家浇，反之不行。

（好吧可能我的敘述方式有點問題慈鸠，還是把代碼貼出來蓝谨，講道理代碼也丑）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int pre[30];
int in[30],out[30],n,ans[30];// ans用來記錄in與out相減的值。
char word[1010];
int judge[30];  //判斷字母是否出現(xiàn)過青团，出現(xiàn)過為1，否則為0咖楣。

int Find(int x)
{
    if(pre[x] < 0) return x;
    return pre[x] = Find(pre[x]);
}

int Union(int R1 , int R2)
{
    int r1 = Find(R1) , r2 = Find(R2);
    int temp = pre[r1] + pre[r2];
    if(pre[r1] > pre[r2])
    {
        pre[r1] = r2; pre[r2] = temp;
    }
    else
    {
        pre[r2] = r1 ; pre[r1] = temp;
    }
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(in,0,sizeof(in));
        memset(out,0,sizeof(out));
        memset(word,0,sizeof(word));
        memset(judge,0,sizeof(judge));
        memset(pre,-1,sizeof(pre));
        scanf("%d",&n);
        for(int i = 1 ; i <= n ;i++)
        {
            scanf("%s",word);
            int len = strlen(word);
            judge[word[0]-'a'+1]=1 ;
            judge[word[len-1]-'a'+1]=1;//將首尾字母記錄為出現(xiàn)過督笆。

            in[word[0]-'a'+1]++;
            out[word[len-1]-'a'+1]++;
            if(Find(word[0]-'a'+1) != Find(word[len-1]-'a'+1))
            {
                Union(word[0]-'a'+1,word[len-1]-'a'+1);   //若首尾字母不同則合并。
            }
        }
        for(int i = 0 ; i < 30 ; i++)
        {
            ans[i] = in[i] - out[i];         //將所有字母入度和出度的值記錄下來诱贿。
        }
        int co1 = 0 , co2 = 0 , flag = 1;
        for(int i = 0 ; i < 30 ; i++)        //從這里開始判斷是否只有一個-1娃肿，一個1咕缎，其余全為0的情況。
        {
            if(ans[i]!=0&&ans[i]!=-1&&ans[i]!=1)
            {
                flag = 0;
                break;
            }
            if(ans[i]==-1)
            {
                co1++;
                if(co1 > 1)
                {
                    flag = 0;
                    break;
                }
            }
            if(ans[i]==1)
            {
                co2++;
                if(co2>1)
                {
                    flag = 0; break;
                }
            }
        }
        if(flag == 0)                          //不滿足則退出
        {
            printf("The door cannot be opened.\n"); continue;
        }
        int con = 0;
        for(int i = 0 ; i < 30  ; i++)          //記錄出現(xiàn)過字母的個數(shù) 料扰。
        {
            if(judge[i]) con++;
        }
        flag = 0;
        for(int i = 0 ; i < 30 ; i++)            //判斷與最長鏈的節(jié)點個數(shù)是否相等凭豪。
        {
             if(pre[i]==(-1)*con)
             {
                 flag = 1;break;
             }
        }
        if(flag == 1) printf("Ordering is possible.\n");
        else printf("The door cannot be opened.\n");


    }
}