按字母来建边，每个单词的首字母和尾字母加边。先判断是否连通，，然后判断每个字母的入度和出度不能出现差的绝对值大于2，然后入度和出度差的绝对值为1的不能超过两个。就可以形成欧拉路径
代码如下：
#include <iostream>#include <string.h>#include <math.h>#include <queue>#include <algorithm>#include <stdlib.h>#include <map>#include <set>#include <stdio.h>using namespace std;#define LL long long#define pi acos(-1.0)const int mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;const int MAXN=100000+10;char s[1100];int in[30], out[30], bin[30], _hash[30], f[30], vis[30];int find1(int x){return bin[x]==x?x:bin[x]=find1(bin[x]);}void join(int x, int y){int f1=find1(bin[x]);int f2=find1(bin[y]);if(f1!=f2){bin[f2]=f1;}}void init(){memset(in,0,sizeof(in));memset(out,0,sizeof(out));memset(_hash,0,sizeof(_hash));memset(vis,0,sizeof(vis));for(int i=0;i<25;i++){bin[i]=i;}}int main(){int t, n, i, len, sum, cnt, x;scanf("%d",&t);while(t–){scanf("%d",&n);init();cnt=0;for(i=0;i<n;i++){scanf("%s",s);len=strlen(s);in[s[len-1]-'a']++;out[s[0]-'a']++;join(s[0]-'a',s[len-1]-'a');vis[s[0]-'a']=vis[s[len-1]-'a']=1;}for(i=0;i<25;i++){if(!vis[i]) continue ;x=find1(bin[i]);if(!_hash[x]){_hash[x]=1;cnt++;}}if(cnt>1) puts("The door cannot be opened.");else{sum=0;bool flag=0;for(i=0;i<25;i++){if(abs(in[i]-out[i])==1){sum++;}else if(abs(in[i]-out[i])>1){flag=1;}}if(sum>2||flag) puts("The door cannot be opened.");else puts("Ordering is possible.");}}return 0;}
只有一条路不能拒绝——那就是成长的路。
