本文借鑒大神博客
歐拉環(huán)與歐拉路徑的判斷求法

定義：一個有向圖是半歐拉圖當且僅當該圖的基圖是連通的且有且只有一個點的入度比出度少1（作為歐拉路徑的起點）丽已，有且只有一個點的入度比出度多1（作為終點）传藏，其余點的入度等于出度缨叫。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define CLR(x) memset(x,0,sizeof(x))
#define maxn 30
#define longest 1010
using namespace std;

int T,N;
int Father[maxn];
int vis[maxn],out[maxn],in[maxn];             //存儲入度點與出度點
int len,sta,fin;                              //字符串長度，起點，終點
int innum, outnum,root;                       //存儲總入度與出度值
char str[longest];

int Find(int x)
{
    if(Father[x] == x) return x;
    else return Find(Father[x]);
}

void Union(int a, int b)
{
    int A = Find(a), B = Find(b);
    if(A != B) Father[B] = A;
}

void ini()                                          //初始化
{
    for(int i=0; i<maxn; i++)
    {
        Father[i] = i;
    }
    CLR(vis);CLR(out);CLR(in);
    innum=0,outnum=0,root=0;
}


int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&N)脚翘；
        ini();
        for(int i=0; i<N; i++)
        {
            scanf("%s",str);
            len = strlen(str);
            sta = str[0]-'a'+1; fin = str[len-1]-'a'+1;
            vis[sta] = 1,vis[fin] = 1;
            out[sta]++, in[fin]++;
            Union(sta,fin);                                     //構建聯(lián)通圖
        }
        int flag=1,flag1=1;
        for(int i=1; i<maxn; ++i)
        {
            if(vis[i])
            {
                if(Father[i] == i) root++;                                //判斷連通分量
                if(in[i] != out[i])
                {
                    if(in[i] - out[i] == 1) innum++;                      //找到有向半歐拉圖的起點
                    else if(out[i] - in[i] == 1) outnum++;                //找到有向半歐拉圖的終點
                    else flag1 = 0;
                }
            }
            if(root > 1){flag = 0;break;}                                 //有不連通部分
        }
        if((flag && innum == 0 && outnum == 0 && flag1/*有向歐拉環(huán)*/) || (flag && innum == 1 && outnum == 1 && flag1/*有向半歐拉圖*/))
            printf("Ordering is possible.\n");
        else
            printf("The door cannot be opened.\n");
    }
    return 0;
}