题目总体没有难度，做法明确，数据较小。单词做边，首尾字母为点构图。构造output a line giving the lexicographically least compound catenym that contains each dictionary word exactly once 的方法边是每次取边的时候贪心的选择字典序最小的单词。可以用并查集事先判连通和存在性，再求欧拉迹。
      顺便练习了一下多重集MultiSets的使用，用平衡树保持边集的字典序以实现lgn时间内插入和删除，由于set不支持键的修改，只能直接在树中删边。

      
 1#include<cstdio>
 2#include<cstring>
 3#include<set>
 4#include<stack>
 5#include<string>
 6using namespace std;
 7struct nod{
 8    char str[22];
 9     bool operator < (const nod &a)const{
10         return strcmp(a.str,str)>0;
11     }
12}arr[1111];
13multiset<struct nod> _set[26];
14multiset<struct nod>::iterator it;
15stack<string> _sta;
16int degree[26][2];
17int hash[26];
18
19void solve(int s){
20    int k;
21    string str;
22    while(!_set[s].empty()){
23        it=_set[s].begin();
24        k=(*it).str[strlen((*it).str)-1]-'a';
25        str=(*it).str;
26        _set[s].erase(it);    
27        solve(k);
28        _sta.push(str);
29    }
30}
31
32int main(){
33    string ss;
34    bool flag;
35    int _case,n,num,i,s,t;
36    int inNum,outNum,inPos,outPos;
37    scanf("%d",&_case);
38    while(_case--){
39        memset(degree,0,sizeof(degree));
40        memset(hash,0,sizeof(hash));
41        while(!_sta.empty()) _sta.pop();
42        for(i=0;i<26;i++) _set[i].clear();
43        
44        scanf("%d",&n); getchar();
45        for(i=0;i<n;i++){
46            gets(arr[i].str);
47            s=arr[i].str[0]-'a';
48            t=arr[i].str[strlen(arr[i].str)-1]-'a';
49            _set[s].insert(arr[i]);
50            hash[s]=hash[t]=1;
51            degree[s][0]++; // out
52            degree[t][1]++; // in
53        }
54        for(flag=true,inNum=outNum=i=0;i<26;i++)
55            if(degree[i][0]!=degree[i][1])
56                if(degree[i][0]==degree[i][1]+1){
57                    outNum++;
58                    outPos=i;
59                }
60                else{
61                    if(degree[i][1]==degree[i][0]+1){
62                        inNum++;
63                        inPos=i;
64                    }
65                    else{
66                        flag=false;
67                        break;
68                    }
69                }
70        if(!flag){ printf("***\n"); continue; }
71        if(inNum==0&&outNum==0){
72            for(i=0;i<26;i++) if(hash[i]) break;
73            solve(i);
74        }
75        if(inNum==1&&outNum==1) solve(outPos);
76        
77        if(_sta.size()==n){  /* 基图连通 */
78            ss=_sta.top(); _sta.pop(); printf(ss.c_str());
79            while(!_sta.empty()){
80                ss=_sta.top(); _sta.pop();
81                printf("."); printf(ss.c_str());
82            }printf("\n");
83        }
84        else printf("***\n");
85    }
86    return 0;
87}