成语接龙可以抽象为欧拉回路，单词为有向边，词头词尾为节点，用dfs判断是否图是否连通，先判断入度出度，然后dfs，在判断图是否连通。visitedv数组用来区别不存在的点、存在的点和存在且已用dfs访问过的点
#include <cstdio> #include <cstring> #include <vector> #include <queue> #include <iostream> using namespace std; #define DEBUG const int maxn=1000+5,maxv=26; int n,startcnt,endcnt,startv,endv; char s[maxn]; int in[26],out[26],visitedv[26]; bool visited[26][26],G[26][26],flag; bool dfs(int u){ visitedv[u]=2; for(int v=0;v<maxv;v++){ if(G[u][v]&&!visited[u][v]){ visited[u][v]=1; dfs(v); // printf("%d %d\n",u,v); } } return true; } int main(){ #ifdef DEBUG freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif int m; cin>>m; while(m--){ memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); memset(visited,0,sizeof(visited)); memset(G,0,sizeof(G)); memset(visitedv,0,sizeof(visitedv)); startcnt=0; endcnt=0; cin>>n; while(n--){ cin>>s; int len=strlen(s); visitedv[s[0]-'a']=visitedv[s[len]-'a']=1; G[s[0]-'a'][s[len-1]-'a']=1; in[s[0]-'a']++;out[s[len-1]-'a']++; } flag=1; for(int i=0;i<26;i++){ if(in[i]!=out[i]){ if(in[i]==out[i]+1) startv=i,startcnt++; else if(in[i]+1==out[i]) endv=i,endcnt++; else{flag=0;break;} } if(!startcnt&&in[i]) startv=i; } if(endcnt>1||startcnt>1)flag=0; if(!flag){cout<<"The door cannot be opened.\n";continue;} // printf("startv:%d\n",startv); // printf("endv:%d\n",endv); dfs(startv); flag=1; for(int i=0;i<26;i++) if(visitedv[i]==1){flag=0;cout<<"The door cannot be opened.\n";break;} if(flag) cout<<"Ordering is possible.\n"; } #ifdef DEBUG fclose(stdin); fclose(stdout); #endif return 0; }