/*
NYOJ 99单词拼接:
思路：欧拉回路或者欧拉路的搜索！
注意：是有向图的！不要当成无向图，否则在在搜索之前的判断中因为判断有无导致不必要的搜索，以致TLE!
有向图的欧拉路：abs(In[i] - Out[i])==1(入度[i] - 出度[i])的节点个数为两个
有向图的欧拉回路：所有的节点都有In[i]==Out[i]
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
char s[35];
int first, end;
};
bool cmp(node a, node b){
return strcmp(a.s, b.s) <0;
}
node nd[1005];
int In[30], Out[30];
int order[1005], vis[1005];
int n;
int fun(){
memset(vis, 0, sizeof(vis));
int i;
int last=-1;
int first=-1;
//有向图欧拉路的判断
for(i=0; i<26; ++i)
{
if(In[i]!=Out[i])
{ //首先入度和出度之差的绝对值为 1的节点的要么没有，要么只有两个（没有欧拉回路，只有欧拉路）！
if(Out[i]-In[i]==1 && first==-1)
first=i;
else if(Out[i]-In[i]==-1 && last==-1)
last=i;
else
return -1;
}
}
if(first>-1 && last>-1) //这种情况是 欧拉路的搜索 ！
return first;
else if(first==-1 && last==-1) //这种是欧拉回路的搜索！
{
for(i=0; i<26; ++i)
if(In[i]!=0)
return i;
}
else
return -1;
}
bool dfs(int st, int cnt){
if(cnt == n)
return true;
int ld=0, rd=n-1;
while(ld<=rd){
int mid=(ld+rd)/2;
if(nd[mid].first<st)
ld=mid+1;
else rd=mid-1;
}
int m=rd+1;
if(nd[m].first > st) return false;
for(int i=m; i<n; ++i)
if(!vis[i]){
if(nd[i].first > st)
return false;
if(nd[i].first == st){
vis[i]=1;
order[cnt]=i;
if(dfs(nd[i].end, cnt+1)) return true;
vis[i]=0;
}
}
return false;
}
int main(){
int t;
scanf("%d", &t);
while(t--){
scanf("%d", &n);
memset(In, 0, sizeof(In));
memset(Out, 0, sizeof(Out));
for(int i=0; i<n; ++i){
scanf("%s", nd[i].s);
nd[i].first=nd[i].s[0]-'a';
nd[i].end=nd[i].s[strlen(nd[i].s)-1]-'a';
++Out[nd[i].first];
++In[nd[i].end];
}
int st = fun();
//因为搜索的是字典序的第一个，所以将字符串从小到大排一下序！在搜索的时候按照升序搜索组合！
sort(nd, nd+n, cmp);
if(st==-1 || !dfs(st, 0))
printf("***\n");
else{
printf("%s", nd[order[0]].s);
for(int i=1; i<n; ++i)
printf(".%s", nd[order[i]].s);
printf("\n");
}
}
return 0;
}
本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3900428.html，如需转载请自行联系原作者
![【Day21】LeetCode算法题 [921. 使括号有效的最少添加 ] [1706. 球会落何处]](https://ucc.alicdn.com/pic/developer-ecology/7fcd1648d721423d9ca72be31307a8a7.png?x-oss-process=image/resize,h_160,m_lfit)
![【Day30】LeetCode算法 [769. 最多能完成排序的块 ] [2131. 连接两字母单词得到的最长回文串]](https://ucc.alicdn.com/pic/developer-ecology/5fe4d27c543442b4bf43e91d33e86620.png?x-oss-process=image/resize,h_160,m_lfit)