题目
https://www.luogu.org/problemnew/show/P1127
思路
1.单词作点 可以拼在一起的单词连边。
2.先对单词排序，加边时注意顺序，使找到的第一个欧拉回路即为字典序最小的，后面直接跳出就好了。
3.dfs前初步判断一下是否有解（注意，是初步！！！） 用一些奇怪的方法
4.dfs后，若找到解则输出，否则***。（因为初步判断有解时可能将一些无解的情况放过了）
代码
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int N=1010,inf=1<<29;
int n,len[N],sta[N],cnt[30],top=0;
int head[N],to[N*N],next[N*N],en;
bool flag=false,vis[N];
string s[N];
void dfs(int u)
{
if (flag) return ;
sta[top++]=u;
vis[u]=true;
int v;
for (int i=head[u];i;i=next[i])
{
v=to[i];
if (!vis[v]) dfs(v);
}
if (top==n) flag=true;
else vis[u]=false,--top;
}
void add_edge(int u,int v){
to[++en]=v,next[en]=head[u],head[u]=en;
}
int main()
{
cin>>n;
for (int i=1;i<=n;i++)
cin>>s[i];
sort(s+1,s+n+1);
for (int i=1;i<=n;i++)
len[i]=s[i].size();
for (int i=1;i<=n;i++)
for (int j=n;j>=1;j--)
if (i!=j && s[i][len[i]-1]==s[j][0])
add_edge(i,j);
for (int i=1;i<=n;i++)
cnt[s[i][0]-'a']++,cnt[s[i][len[i]-1]-'a']--;
int k=0,h;
for (int i=0;i<26;i++){
if (cnt[i]==1) k++,h=i;
if (cnt[i]==2) k=2;
if (k==2) break;
}
if (k==2) cout<<"***\n";
else if (k==1){
for (int i=1;i<=n;i++)
if (s[i][0]-'a'==h)
dfs(i);
}
else {
for (int i=1;i<=n;i++)
dfs(i);
}
if (!flag) {
cout<<"***\n";
return 0;
}
cout<<s[sta[0]];
for (int i=1;i<top;i++)
cout<<'.'<<s[sta[i]];
cout<<endl;
return 0;
}
