POJ 2337 Catenyms（欧拉回（通）路：路径输出+最小字典序）

题目大意：给你n个字符串，只有字符串首和尾相同才能连接起来。请你以最小字典序输出连接好的单词。

解题思路：跟POJ1386一个意思，就是把26个字母当成点，单词当做有向边，判断欧拉回（通）路。但是要输出路径也就是单词，而且要求字典序最小。

可以通过将单词先排序再添加边使字典序最小，还有注意起点，如果有一个出度比入度大1的点，就从这个点出发，否则从最小的点出发。

代码：

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstdio>
  4 #include<cstring>
  5 #include<string>
  6 #include<stack>
  7 #define CLR(arr,val) memset(arr,val,sizeof(arr))
  8 #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
  9 using namespace std;
 10 const int M=2e4+5;
 11 const int N=1e4+5;
 12 
 13 struct node{
 14     int to,next;
 15     string w;
 16 }edge[M];
 17 
 18 int idx;
 19 int indeg[N],outdeg[N],head[N];
 20 string str[M];
 21 bool vis[M];
 22 stack<string>sk;
 23 
 24 void init(){
 25     idx=1;
 26     CLR(head,0);
 27     CLR(indeg,0);
 28     CLR(outdeg,0);
 29     CLR(vis,false);
 30     while(!sk.empty()){
 31         sk.pop();
 32     }
 33 }
 34 
 35 void addedge(int u,int v,string w){
 36     edge[idx].to=v;
 37     edge[idx].w=w;
 38     edge[idx].next=head[u];
 39     head[u]=idx++;
 40 }
 41 
 42 void dfs(int u){
 43     for(int &j=head[u];j;j=edge[j].next){
 44         node t=edge[j];
 45         if(!vis[j]){
 46             vis[j]=true;
 47             dfs(t.to);
 48             sk.push(t.w);
 49         }
 50     }
 51 }
 52 
 53 int main(){
 54     FAST_IO;
 55     int t;
 56     cin>>t;
 57     while(t--){
 58         init();
 59         int n;
 60         cin>>n;
 61         for(int i=0;i<n;i++)
 62             cin>>str[i];
 63         sort(str,str+n);
 64         int start=100;
 65         //字典序大的先加入，因为静态邻接表是反向添加的 
 66         for(int i=n-1;i>=0;i--){
 67             int u,v;
 68             u=str[i][0]-'a';
 69             v=str[i][str[i].length()-1]-'a';
 70             outdeg[u]++;
 71             indeg[v]++;
 72             addedge(u,v,str[i]);
 73             start=min(start,min(u,v));
 74         }
 75         int chu=0,ru=0;
 76         bool flag=true;
 77         for(int i=0;i<26;i++){
 78             if(indeg[i]+outdeg[i]==0)
 79                 continue;
 80             if(indeg[i]!=outdeg[i]){
 81                 if(indeg[i]+1==outdeg[i]){
 82                     chu++;
 83                     start=i;                //如果有一个出度比入度大1的点，就从这个点出发，否则从最小的点出发
 84                 }
 85                 else if(indeg[i]-1==outdeg[i])
 86                     ru++;
 87                 else
 88                     flag=false;
 89             }
 90         }
 91         if(flag&&(chu==1&&ru==1||chu==0&&ru==0)){
 92             dfs(start);
 93             if(sk.size()==n){
 94                 while(!sk.empty()){
 95                     if(sk.size()==1)
 96                         cout<<sk.top()<<endl;
 97                     else
 98                         cout<<sk.top()<<".";
 99                     sk.pop();
100                 }
101             }
102             else
103                 puts("***");
104         }
105         else
106             puts("***");
107     }
108     return 0;
109 }