这1题，相比之前做的题目，增加了欧拉路径的求解。而且这1题是有向图。题目大概的意思就是成语接龙，能接起来就算可以打开门，因此要斟酌两种，1种是回路，另外1种是1条路径。
第1次WR就是由于没有斟酌回路这1个因素。
有向图中，欧拉回路与欧拉路径的求解方法：
1.欧拉回路：
首先固然是图连通，其次就是所以顶点的入度都等于出度。
2.欧拉路径：
重要的还是图连通，然后就是存在1个顶点的出度大入度1，存在1个顶点的入度大出度1，其他顶点的入度等于出度。
这些就不再证明。图的连通可以用DFS来判断或并查集，个人喜欢并查集。
下面是AC的代码，有详细的注释：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int par[30], indegree[30], outdegree[30]; //par为并查集，indegree为入度，outdegree为出度
bool vis[30]; //vis为该顶点出现过的标记
int finds(int x) //并查集的查找函数
{
int r = x;
while(r != par[r])
r = par[r];
int i = x, j;
while(i != r) //路径紧缩
{
j = par[i];
par[i] = r;
i = j;
}
return r;
}
void join(int x, int y) //并查集的合并函数
{
int fx = finds(x);
int fy = finds(y);
if(fx != fy)
par[fy] = fx;
}
int main()
{
int t, n, i;
char str[1005];
scanf("%d", &t);
while(t--)
{
memset(indegree, 0, sizeof(indegree)); //初始化各个数组
memset(outdegree, 0, sizeof(outdegree));
memset(vis, false, sizeof(vis));
for(i = 0; i < 30; i++) //初始化并查集
par[i] = i;
scanf("%d", &n);
while(n--)
{
scanf("%s", str);
int len = strlen(str);
join(str[0] - 'a', str[len - 1] - 'a'); //合并出现的顶点
indegree[str[len - 1] - 'a']++; //相应的入度+1
outdegree[str[0] - 'a']++; //相应的出度+1
vis[str[0] - 'a'] = true; //标记该顶点出现过
vis[str[len - 1] - 'a'] = true;
}
int flag = 0, tag = 0, a = 0, b = 0; //flag来判图是不是连通，tag为图中顶点入度不等于出度的个数
<span style="white-space:pre"> </span>//a为入度大出度1的点的个数，b为出度大入度1的点的个数
for(i = 0; i < 30; i++) //判连通
{
if(vis[i] && par[i] == i)
flag++;
}
if(flag > 1) //不连通，直接输出
{
printf("The door cannot be opened.
");
}
else
{
for(i = 0; i < 30; i++) //查找tag，a， b 的个数
{
if(vis[i] && indegree[i] != outdegree[i])
{
tag++;
}
if(vis[i] && indegree[i] - outdegree[i] == 1)
a++;
if(vis[i] && outdegree[i] - indegree[i] == 1)
b++;
}
if(tag == 0) //tag = 0，存在欧拉回路
printf("Ordering is possible.
");
else if(a == b && a == 1 && tag == 2) //a = 1 && b = 1 && tag = 2.存在欧拉路径
printf("Ordering is possible.
");
else
printf("The door cannot be opened.
");
}
}
return 0;
}