题意：给n个字符串（3<=n<=1000），当字符串str[i]的尾字符与str[j]的首字符一样时，可用dot连接。判断用所有字符串一次且仅一次，连接成一串。若可以，输出答案的最小字典序（dot是最小字典序的，比‘a'小）。
显然就是以26个字母为结点，n个字符串为边，求解有向图的欧拉通路。
不过这里要注意，26个字母不一定都用上。
先判断有向图的欧拉通路的条件是否成立：
1.有一个结点入度等于出度+1且有一个结点出度等于入度+1且其他结点入度等于出度。（或所有结点入度等于出度）
2.有向图的基图连通。（把有向边改成无向边后，图连通）
感觉中间那段while（top）可以当做模板来用了，具体机理这里不详细说了，看着想一想还是能理解的。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <queue>
#include <map>
#include <stack>
using namespace std; #define MP make_pair
#define ll long long
#define inf 0x3f3f3f3f int in[30],out[30];
struct Edge{
int v,nxt;
bool vis;
}e[1010];
int head[30],esz;
void addedge(int u,int v){
e[esz].v=v,e[esz].nxt=head[u];
e[esz].vis=false;
head[u]=esz++;
}
int fa[30];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
bool jud(){
for(int i=0;i<26;++i) fa[i]=i;
int st;
for(int u=0;u<26;++u){
for(int j=head[u];j!=-1;j=e[j].nxt){
int v = e[j].v;
st = fa[find(u)] = find(v);
}
}
for(int i=0;i<26;++i){
if(out[i]+in[i] && find(i)!=find(st)) return false;
}
return true;
}
int main(){
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
string s[1010];
for(int i=0;i<n;++i){
char tmp[22];
scanf("%s",tmp);
s[i] = tmp;
}
sort(s,s+n);
memset(in,0,sizeof(in));
memset(out,0,sizeof(out));
queue<string>val[30][30];
esz=0; memset(head,-1,sizeof(head));
for(int i=n-1;i>=0;--i){
int u = s[i][0]-'a', v = s[i][s[i].size()-1]-'a';
out[u]++; in[v]++;
addedge(u,v);
}
for(int i=0;i<n;++i){
int u = s[i][0]-'a', v = s[i][s[i].size()-1]-'a';
val[u][v].push(s[i]);
}
int j1=-1,j2=-1,j3=1;
for(int i=0;i<26;++i){
if(in[i]==out[i]) continue;
if(out[i]==in[i]+1){
if(j1==-1) j1=i;
else j3=0;
continue;
}
if(in[i]==out[i]+1){
if(j2==-1) j2=i;
else j3=0;
continue;
}
j3=0;
}
if((j1^j2)<0) j3=0;
if(j3==0 || jud()==false){
puts("***");
continue;
}
if(j1==-1){
for(int i=0;i<26;++i){
if(out[i]){
j1=i;
break;
}
}
}
stack<int>st;
vector<int>ans;
st.push(j1);
while(!st.empty()){
int u = st.top(); st.pop();
bool f = false;
for(int i=head[u];i!=-1;i=e[i].nxt){
int v = e[i].v;
if(e[i].vis) continue;
e[i].vis = true;
st.push(u);
st.push(v);
f=true;
break;
}
if(f==false) ans.push_back(u);
}
for(int i=ans.size()-1;i;--i){
int u = ans[i];
int v = ans[i-1];
printf("%s",val[u][v].front().c_str());
val[u][v].pop();
if(i!=1) printf(".");
else puts("");
}
}
return 0;
}