给出n个单词，如果一个单词的尾和另一个单词的头字符相等，那么可以相连，问这n个单词是否可以排成一列。欧拉路应用，构图：一个单词的头尾字母分别作为顶点，每输入一个word，该word的头指向word的尾画一个有向边，并且记录每个顶点的出入度。利用dfs先判断是否为一个连通图，如果是的话则判断是否有且仅有一个起点和终点（abs（出度-入度）=1），或是一个环
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#define maxn 100000+5
using namespace std;
string map[maxn];
int n,chu[],ru[],G[][],vst[],f,ok,c[],cnt,ts;
int init(){
cin>>n;
memset(chu,,sizeof(chu));
memset(ru,,sizeof(ru));
memset(G,,sizeof(G));
memset(vst,,sizeof(vst));
memset(c,,sizeof(c));
cnt=;
string temp;
for (int i=;i<n;i++){
cin>>map[i];
int p,q;
p=map[i][]-'a';
q=map[i][map[i].size()-]-'a';
ts=p;
if (!c[p]) {cnt++;c[p]=;}
if (!c[q]) {cnt++;c[q]=;}
G[p][q]=;
chu[p]++;ru[q]++;
}
}
int is_link(int p){
for (int j=;j<;j++){
if (G[p][j]&&!vst[j]){
vst[j]=;
f++;
is_link(j);
}
}
}
int find_start(){
int i;
for ( i=;i<;i++)
if (chu[i]-ru[i]==) return i;
if (i==) return ts;
//cout<<"find"<<ok<<endl;
}
int work(){
int t=,f=;
for (int i=;i<;i++)
if (chu[i]!=ru[i]){
if (abs(chu[i]-ru[i])==)t++;
else f=;
}
if ((t==&&f==)||(t==)) return ;
return ;
}
int main()
{
int T;
cin>>T;
while (T--){
init();
ok=;
int p;
p=find_start();
vst[p]=;
f=;
if (ok)is_link(p);
if (f!=cnt) ok=;
if (ok) ok=work();
if (ok) cout<<"Ordering is possible."<<endl;
else cout<<"The door cannot be opened."<<endl;
}
}