题意：给出 n 个单词，问能否将所有单词组成一个序列，要求序列的前一个单词的尾字母与后一个单词的头字母相同

思路：实质是求一个有向图是否存在欧拉回路或欧拉通路的问题

由于每个单词只能从单词头走到单词尾，因此将每个单词看成一个有向边，把26个字母看成图的节点，然后求序列就是求是否存在欧拉回路或欧拉通路

若图中所有点的入度等于出度，则存在欧拉回路，若有两个点入度不等于出度，但两者之差的绝对值等于1，则存在欧拉通路。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<ctime>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 1001
#define MOD 16007
#define E 1e-6
#define LL long long
using namespace std;
int m;
int degIn[N],degOut[N];
int father[N];
int Find(int x){
    if(father[x]==-1)
        return x;
    return father[x]=Find(father[x]);
}
void Union(int x,int y){
    x=Find(x);
    y=Find(y);
    if(x!=y)
        father[x]=y;
}
int main(){
 
    int t;
    scanf("%d",&t);
    while(t--){
        memset(degIn,0,sizeof(degIn));
        memset(degOut,0,sizeof(degOut));
        memset(father,-1,sizeof(father));
 
        scanf("%d",&m);
        for(int i=1;i<=m;i++){
            char str[2000];
            scanf("%s",str);
 
            int len=strlen(str);
            int x=str[0]-'a';
            int y=str[len-1]-'a';
 
            degIn[x]++;
            degOut[y]++;
            Union(x,y);
        }
 
        int cnt=0;//统计连通分量
        for(int i=0;i<26;i++)
            if( (degIn[i]||degOut[i]) && (Find(i)==i) )
                    cnt++;
        if(cnt>1)
            printf("The door cannot be opened.\n");
        else{
             //出度不等于入度的三种情况
            int situation1=0;
            int situation2=0;
            int situation3=0;
 
            for(int i=0;i<26;i++)
            {
                if(degIn[i]==degOut[i])
                    continue;
                else if(degIn[i]-degOut[i]==1)
                    situation1++;
                else if(degOut[i]-degIn[i]==1)
                    situation2++;
                else
                    situation3++;
            }
            if( ( (situation1==situation2&&situation1==1)||(situation1==situation2&&situation1==0) )&&situation3==0 )
                printf("Ordering is possible.\n");
            else
                printf("The door cannot be opened.\n");
        }
    }
    return 0;
}