这是一道欧拉回路题
欧拉回路：就是一个路径包括每条边恰好一次。
判断是否满足欧拉回路。首先是图是联通的。其次图中每个点的入度等于出度。如果是欧拉路径的话，满足奇点只能等于2或0，并且对于有向图，奇点的入度和出度差值为1和-1。
#include <iostream>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <stack>
#include <queue>
using namespace std;
const double Pi=3.14159265358979323846;
typedef long long ll;
const int MAXN=+;
const int dx[]={,,,-};
const int dy[]={,-,,};
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
int t;
int in[MAXN];
int out[MAXN];
int mp[MAXN][MAXN];
bool vis1[MAXN];
bool vis2[MAXN]; bool dfs(int v,vector <int> S)
{
for(int i=;i<S.size();i++)
{
if(!vis2[S[i]]&&mp[v][S[i]])
{
vis2[S[i]]=;
dfs(S[i],S);
}
}
}
int main()
{
cin>>t;
while(t--)
{ memset(vis1,,sizeof(vis1));
memset(vis2,,sizeof(vis2));
memset(in,,sizeof(in));
memset(out,,sizeof(out));
memset(mp,,sizeof(mp));
int n;scanf("%d",&n);
vector <int> S;
for(int i=;i<=n;i++)
{
string str;cin>>str;
int len=str.size();
int inc=str[]-'a';
int outc=str[len-]-'a';
mp[inc][outc]=;
vis1[inc]=;vis1[outc]=;
in[inc]++;
out[outc]++;
}
for(int i=;i<;i++) if(vis1[i]) {S.push_back(i);} vector <int> V;
for(int i=;i<;i++)
{
if(in[i]!=out[i]) V.push_back(i);
}
vis2[S[]]=;
dfs(S[],S);
int flag=;
for(int i=;i<;i++) cout <<vis1[i]<<" ";
cout <<endl;
for(int i=;i<;i++) cout <<vis2[i]<<" ";
cout <<endl;
for(int i=;i<;i++)
{
if(vis1[i]!=vis2[i])
{
flag=;
break;
}
}
if(!flag)
printf("The door cannot be opened.\n");
else
{
if(V.size()==)
{
if((out[V[]]-in[V[]])==(in[V[]]-out[V[]])&&abs(out[V[]]-in[V[]])==)
{
printf("Ordering is possible.\n");
}
else printf("The door cannot be opened.\n");
} else printf("The door cannot be opened.\n");
}
}
return ;
}