题目意思：给定n个单词，要求单词的第一个字母和前一个单词的最后字母相同（除了第一个），判断所有单词是否可以连成一条链。
解题思路：题目很明显是一个有关欧拉路的问题，我们先了解一下有关欧拉道路和欧拉回路的区别。欧拉道路是分为有向和无向两种，对于欧拉道路上的节点有两种度，入度和出度，入度表示进入该节点次数，出度表示出去该节点的次数，对于一条普通的有向欧拉道路来说存在一个起点和终点，并且起点的入度比出度小1，终点的入度比出度大1，下面介绍特殊的欧拉道路-----欧拉回路，欧拉回路是起点和终点重合，并且所有的节点的度都相同都为偶数。
有了这些知识，介绍解题方法，首先我们用两个数组in out来存储每个单词的首字母和末尾字母的入度和出度，还用一个map二维数组作为点的邻阶矩阵。
第一步 读完字符串后判断是否可以构成欧拉道路，利用性质判断，即每一个节点的入度和出度差的范围是-1～1，超过这个范围即可判断不满足。
第二步 如果是欧拉道路的话，我们可以用dfs来搜索第一个有出度的单词，这时候的搜索是不用考虑方向的，即用到我们刚才建的map二维数组，用一个同一大小的 二 维数组记录走过的单词，如果刚好把map对应的单词全部标记，说明已经可以链接成一条链。（这里可以用并查集）
注意事项：对于欧拉道路来说，是否是连通的就是判断从某个点能否遍历所有的点，这时候要建立一个无向图的邻阶矩阵（判断连通都是当成无向图判断）
代码：
//对于欧拉道路来说，是否是连通的就是判断从某个点能否遍历所有的点，这时候要建立一个无向图的邻阶矩阵（判断连通都是当成无向图判断）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
const int MAXN = 30;
int t, n, flag;
int out[MAXN], in[MAXN];
int vis[MAXN][MAXN] , map[MAXN][MAXN];
//深搜
void dfs(int pos) {
for(int i = 0 ; i < 26 ; i++){
if(map[pos][i] && vis[pos][i] == 0){
vis[pos][i] = 1;//标记为1
dfs(i);//继续搜索
}
}
}
void solve() {
int i , j , cnt;
flag = 1;//初始化为1
for (i = 0; i < 26; i++) {//判断是否满足欧拉道路的性质
if (out[i] - in[i] < -1 || out[i] - in[i] > 1){
flag = 0;
return;
}
}
for(i = 0 ; i < 26 ; i++){
if(out[i]){//找到一个有出度的直接搜索
dfs(i);
break;//这里要跳出循环
}
}
for(i = 0 ; i < 26 ; i++){
for(j = 0 ; j < 26 ; j++){
if(map[i][j] && vis[i][j] == 0){//判断是否可以连成链
flag = 0;
return;
}
}
}
}
int main() {
int i;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
string str;
memset(out, 0, sizeof (out));
memset(in, 0, sizeof (in));
memset(map , 0 , sizeof(map));
memset(vis , 0 , sizeof(vis));
for (i = 0; i < n; i++) {
cin>>str;
int len = str.size();
int x = str[0] - 97;
int y = str[len-1] - 97;
out[x]++;
in[y]++;
//无向图的邻阶矩阵
map[x][y]++;
map[y][x]++;
}
if (n == 1)//对于1的特判
flag = 1;
if (n > 1)
solve();
if (flag)
printf("Ordering is possible.\n");
if (flag == 0)
printf("The door cannot be opened.\n");
}
}
