1 /*  2    NYOJ 99单词拼接:  3    思路：欧拉回路或者欧拉路的搜索！  4    注意：是有向图的！不要当成无向图，否则在在搜索之前的判断中因为判断有无导致不必要的搜索，以致TLE!  5    有向图的欧拉路：abs(In[i] - Out[i])==1(入度[i] - 出度[i])的节点个数为两个   6    有向图的欧拉回路：所有的节点都有In[i]==Out[i]   7 */   8 #include<iostream>  9 #include<cstring> 10 #include<cstdio> 11 #include<algorithm> 12 using namespace std; 13  14 struct node{ 15    char s[35]; 16    int first, end; 17 }; 18  19 bool cmp(node a, node b){ 20    return strcmp(a.s, b.s) <0; 21 } 22  23 node nd[1005]; 24 int In[30], Out[30]; 25 int order[1005], vis[1005];  26 int n; 27  28 int fun(){ 29     memset(vis, 0, sizeof(vis)); 30     int i;   31     int last=-1;   32     int first=-1;   33     //有向图欧拉路的判断  34     for(i=0; i<26; ++i)   35     {   36         if(In[i]!=Out[i])   37         {   //首先入度和出度之差的绝对值为 1的节点的要么没有，要么只有两个（没有欧拉回路，只有欧拉路）！  38             if(Out[i]-In[i]==1 && first==-1)   39                 first=i;   40             else if(Out[i]-In[i]==-1 && last==-1)   41                 last=i;   42             else   43                 return -1;   44         }   45     }   46     if(first>-1 && last>-1) //这种情况是 欧拉路的搜索 ！  47         return first;   48     else if(first==-1 && last==-1) //这种是欧拉回路的搜索！  49     {   50         for(i=0; i<26; ++i)   51             if(In[i]!=0)   52                 return i;   53     }   54     else   55         return -1;   56 } 57  58 bool dfs(int st, int cnt){  59    if(cnt == n) 60       return true;  61    int ld=0, rd=n-1; 62    while(ld<=rd){ 63        int mid=(ld+rd)/2; 64        if(nd[mid].first<st) 65            ld=mid+1; 66        else rd=mid-1;  67    } 68    int m=rd+1; 69    if(nd[m].first > st) return false; 70    for(int i=m; i<n; ++i) 71       if(!vis[i]){           72             if(nd[i].first > st) 73                return false; 74             if(nd[i].first == st){ 75               vis[i]=1; 76               order[cnt]=i; 77               if(dfs(nd[i].end, cnt+1)) return true;  78               vis[i]=0;     79           } 80       }  81    return false; 82 } 83  84  85 int main(){ 86    int t; 87    scanf("%d", &t); 88    while(t--){ 89       scanf("%d", &n); 90       memset(In, 0, sizeof(In)); 91       memset(Out, 0, sizeof(Out)); 92       for(int i=0; i<n; ++i){ 93          scanf("%s", nd[i].s); 94          nd[i].first=nd[i].s[0]-‘a‘; 95          nd[i].end=nd[i].s[strlen(nd[i].s)-1]-‘a‘; 96          ++Out[nd[i].first]; 97          ++In[nd[i].end]; 98       }  99         100          int st = fun();101          //因为搜索的是字典序的第一个，所以将字符串从小到大排一下序！在搜索的时候按照升序搜索组合！ 102          sort(nd, nd+n, cmp);103          if(st==-1 || !dfs(st, 0))104             printf("***\n");105          else{106             printf("%s", nd[order[0]].s);107             for(int i=1; i<n; ++i)108                printf(".%s", nd[order[i]].s);109             printf("\n");110          } 111    }112    return 0;113 }