给你一些单词，请你判断能否把它们首尾串起来串成一串。
前一个单词的结尾应该与下一个单词的道字母相同。
如
aloha
dog
arachnid
gopher
tiger
rat
可以拼接成：aloha.arachnid.dog.gopher.rat.tiger
输入 第一行是一个整数N(0<N<20)，表示测试数据的组数 每组测试数据的第一行是一个整数M,表示该组测试数据中有M(2<M<1000)个互不相同的单词，随后的M行，每行是一个长度不超过30的单词,单词全部由小写字母组成。 输出 如果存在拼接方案，请输出所有拼接方案中字典序最小的方案。(两个单词之间输出一个英文句号".") 如果不存在拼接方案，则输出 *** 样例输入 2 6 aloha arachnid dog gopher rat tiger 3 oak maple elm 样例输出 aloha.arachnid.dog.gopher.rat.tiger *** 来源 Waterloo local 2003.01.25 /POJ 上传者张云聪
注释自己理解就好，我写的不一定对。
#include<stdio.h> #include<string.h> #include<stdlib.h> #define maxn 1010 struct node{ int to; }e[30][100];//边 int indegree[30]; int outdegree[30]; int next[maxn]; char str[maxn][35]; int que[maxn]; bool vis[maxn]; int m;//字符串数 int count;//节点数 int top; int cmp(const void *a,const void *b) { return strcmp((char *)a,(char *)b); } void init() { for(int i=0;i<30;i++) e[i][0].to=0;//字母 i与其他字母相连的边数 memset(indegree,0,sizeof(indegree)); memset(outdegree,0,sizeof(outdegree)); memset(vis,0,sizeof(vis)); count=m;top=0; } bool dfs(int u,int c) { if(c==count) return true; for(int i=1;i<=e[u][0].to;i++) { node &E=e[u][i]; if(!vis[E.to]) { vis[E.to]=1; que[top++]=E.to;//保存欧拉图的顺序 if(dfs(next[E.to],c+1)) return true; top--; vis[E.to]=0; } } return false; } int main() { int t,i; scanf("%d",&t); while(t--) { scanf("%d",&m); int l,r;//存单词首尾字母 init(); for(i=0;i<m;i++) scanf("%s",str[i]); qsort(str,m,sizeof(str[0]),cmp);//先按字典序排列 for(i=0;i<m;i++) { l=str[i][0]-'a'; int k=++e[l][0].to;//记录与第l个字母相连的边数 e[l][k].to=i;//记录与l结点相连的第k条边的位置 r=strlen(str[i])-1; next[i]=str[i][r]-'a';//记录下一个开始的顶点 outdegree[l]++;indegree[next[i]]++; } int flag=0; for(i=0;i<26;i++) if(indegree[i]!=outdegree[i]) flag++; if(flag!=2&&flag!=0) { printf("***\n"); continue; } if(flag==2)//欧拉通路 { for(i=0;i<26;i++) { if(outdegree[i]-1==indegree[i]) {//头结点 dfs(i,0); break; } } } else dfs(0,0);//欧拉通路 if(top!=m) { printf("***\n"); continue; } for(i=0;i<top-1;i++) printf("%s.",str[que[i]]); printf("%s\n",str[que[top-1]]); } return 0; }