这题除了欧拉回路以外就是个并查集+dfs板子题,唯一难点是欧拉回路
核心考点应该是建图,我们知道一个单词由首字母指向尾字母,这两个字母看作图的节点,把单词从首字母到尾字母的部分看作一条有向边,这样就构成了一个有向图
对于一个有向图,每个节点有两个属性叫入度和出度,入度就是有几条边连进来了,出度就是有几条边从这里出去了,我们可以在建图的时候统计这两个数据
然后是欧拉路径的概念
欧拉路径类似于一笔画游戏
对于欧拉通路,起点的出度比入度多1,终点的入度比出度多1,这样才能保证一笔画完
对于欧拉回路,其实是特殊的欧拉通路,它的起点和终点是同一个点,这就导致他每个点入度出度都是一样,题目给出要找字典序最小的情况,那只能每个点都当起点试一下,择优输出

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
using ll=long long;
//边
struct edge{
  int u,v;
  string w;
};
//并查集
//find
int fd(int x,vector<int>& fa){
  if(fa[x]==x) return x;
  return fa[x]=fd(fa[x],fa);
}
//union
void unions(int a,int b,vector<int>& fa){
  int ra=fd(a,fa);
  int rb=fd(b,fa);
  if(ra!=rb) fa[ra]=rb;
}
//dfs
void dfs(int u,const vector<edge>& edges,vector<int> adj[26],vector<bool>& used,vector<string>& p){
  //结束条件:所有边都被访问过
  for(int i:adj[u]){
    if(used[i]) continue;//剪枝
    used[i]=true;//标记
    dfs(edges[i].v,edges,adj,used,p);
    p.emplace_back(edges[i].w);//回溯
  }
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin>>n;
  while(n--){
    //初始化
    int m;
    cin>>m;
    vector<edge> edges;
    vector<int> adj[26];
    vector<int> fa(26);
    for(int i=0;i<26;i++) fa[i]=i;
    int in[26]={0};
    int out[26]={0};
    bool hedge[26]={false};
    //建图
    for(int i=0;i<m;i++){
      string w;
      cin>>w;
      int u=w.front()-'a';
      int v=w.back()-'a';
      edges.emplace_back(edge{u,v,w});
      adj[u].emplace_back(i);
      ++out[u];
      ++in[v];
      hedge[u]=true;
      hedge[v]=true;
      unions(u,v,fa);
    }
    //连通性检查
    set<int> roots;
    for(int i=0;i<26;i++){
      if(hedge[i]) roots.insert(fd(i,fa));
    }
    if(roots.size()>1){
      cout<<"***"<<endl;
      continue;
    }
    //出入度检查
    int srt=-1,srtc=0,endc=0;
    bool ok=true;
    for(int i=0;i<26;i++){
      if(out[i]-in[i]==1){
        srt=i;
        ++srtc;
      }
      else if(in[i]-out[i]==1) ++endc;
      else if(in[i]!=out[i]){
        ok=false;
        break;
      }
    }
    if(!ok||srtc!=endc){
      cout<<"***"<<endl;
      continue;
    }
    bool iscrt=(srtc==0);//判断回路
    //字典序排序
    for(int i=0;i<26;i++){
      sort(adj[i].begin(),adj[i].end(),[&](int a,int b){
        return edges[a].w<edges[b].w;
      });
    }
    //dfs求欧拉通路/回路
    vector<string> ans;
    if(!iscrt){//通路
      vector<bool> used(m,false);
      dfs(srt,edges,adj,used,ans);
      reverse(ans.begin(),ans.end());
    }else{//回路
      for(int i=0;i<26;i++){
        if(adj[i].empty()) continue;
        vector<bool> used(m,false);
        vector<string> p;
        dfs(i,edges,adj,used,p);
        reverse(p.begin(),p.end());
        if(ans.empty()||p<ans) ans=p;
      }
    }
    bool valid=false;
    for(auto& i:ans){
      if(valid) cout<<".";
      cout<<i;
      valid=true;
    }
    cout<<endl;
  }
}