题意：
给定n个单词， 问是否存在一条欧拉通路（如acm，matal，lack）， 如果存在， 输出字典序最小的一条。
分析：
这题可以看作http://www.cnblogs.com/Jadon97/p/7210278.html升级版本（那题只问是否存在， 这题需要输出路径）
判断有向图的欧拉通路， 主要用到出入度的判定和连通性。
有向图欧拉通路判定方法:图连通；除2个端点外其余节点入度=出度；1个端点入度比出度大1；一个端点入度比出度小1 或 所有节点入度等于出度
DFS求解算法：选择一个正确的起点，用DFS算法遍历所有的边（每条边只遍历一次），遇到走不通就回退。在搜索前进方向上将遍历过的边按顺序记录下来，这组边的排列就组成了一条欧拉通路或者回
#include<cstdio>
#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
string word[];
struct node
{
int to, index;
node(int _to, int _index): to(_to), index(_index) {};
};
vector<node> G[];
int degree[], vis[], used[], ans[];
int n, tot;
int st;
int id(int a)
{
return a - 'a';
}
void dfs(int u)
{
// cout << word[index] << "\n";
for(int i = ; i < G[u].size(); i++)
{
int v = G[u][i].to, index = G[u][i].index;
if(!vis[index])
{
vis[index] = ;
dfs(v);
ans[tot++] = index;
}
}
}
bool judge()
{
int cc1 = , cc2 = ; //cc1 出度>入度 cc2 入度>出度
for(int i = ; i < ; i++)
{
if(used[i])
{
if(degree[i] != )
{
if(degree[i] == )
{
cc1++, st = i;//如果出度大于入度， 那么以该点为起点
}
else if(degree[i] == -)
{
cc2++;
}
else
{
return false;
}
}
}
}
if((cc1 || cc2) && cc1 + cc2 != ) //有出度入度不等的点， 而且不止2个
{
return false;
}
return true;
}
int main()
{
// freopen("1.txt","r", stdin);
int T;
cin >> T;
while(T--)
{
for(int i = ; i < ; i++)
G[i].clear();
memset(used, , sizeof(used));
memset(vis, , sizeof(vis));
memset(degree, , sizeof(degree));
tot = ; cin >> n;
for(int i = ; i < n; i++)
{
cin >> word[i];
} sort(word, word + n);
st = ;
for(int i = ; i < n; i++)
{
int u = id(word[i][]), v = id(word[i][word[i].size()-]);
G[u].push_back(node(v,i));
if(u < st)
st = u; //从字典序最小的开始遍历
used[u] = used[v] = ; //记录u，v是用过的
degree[u]++, degree[v]--; //出度++， 入度--
} if(!judge())
{
printf("***\n");
continue;
}
dfs(st);
if(tot != n) //不连通
{
printf("***\n");
continue;
} else
{
cout << word[ans[tot-]];
for(int i = tot - ; i >= ; i--)//反向输出路径
{
cout <<"." << word[ans[i]] ;
}
puts("");
}
}
}