NYOJ 99单词拼接（有向图的欧拉（回）路）

/*
   NYOJ 99单词拼接:
   思路：欧拉回路或者欧拉路的搜索！
   注意：是有向图的！不要当成无向图，否则在在搜索之前的判断中因为判断有无导致不必要的搜索，以致TLE!
   有向图的欧拉路：abs(In[i] - Out[i])==1(入度[i] - 出度[i])的节点个数为两个 
   有向图的欧拉回路：所有的节点都有In[i]==Out[i] 
*/ 
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

struct node{
   char s[35];
   int first, end;
};

bool cmp(node a, node b){
   return strcmp(a.s, b.s) <0;
}

node nd[1005];
int In[30], Out[30];
int order[1005], vis[1005]; 
int n;

int fun(){
    memset(vis, 0, sizeof(vis));
    int i;  
    int last=-1;  
    int first=-1;  
    //有向图欧拉路的判断 
    for(i=0; i<26; ++i)  
    {  
        if(In[i]!=Out[i])  
        {   //首先入度和出度之差的绝对值为 1的节点的要么没有，要么只有两个（没有欧拉回路，只有欧拉路）！ 
            if(Out[i]-In[i]==1 && first==-1)  
                first=i;  
            else if(Out[i]-In[i]==-1 && last==-1)  
                last=i;  
            else  
                return -1;  
        }  
    }  
    if(first>-1 && last>-1) //这种情况是 欧拉路的搜索 ！ 
        return first;  
    else if(first==-1 && last==-1) //这种是欧拉回路的搜索！ 
    {  
        for(i=0; i<26; ++i)  
            if(In[i]!=0)  
                return i;  
    }  
    else  
        return -1;  
}

bool dfs(int st, int cnt){ 
   if(cnt == n)
      return true; 
   int ld=0, rd=n-1;
   while(ld<=rd){
       int mid=(ld+rd)/2;
       if(nd[mid].first<st)
           ld=mid+1;
       else rd=mid-1; 
   }
   int m=rd+1;
   if(nd[m].first > st) return false;
   for(int i=m; i<n; ++i)
      if(!vis[i]){          
            if(nd[i].first > st)
               return false;
            if(nd[i].first == st){
              vis[i]=1;
              order[cnt]=i;
              if(dfs(nd[i].end, cnt+1)) return true; 
              vis[i]=0;    
          }
      } 
   return false;
}


int main(){
   int t;
   scanf("%d", &t);
   while(t--){
      scanf("%d", &n);
      memset(In, 0, sizeof(In));
      memset(Out, 0, sizeof(Out));
      for(int i=0; i<n; ++i){
         scanf("%s", nd[i].s);
         nd[i].first=nd[i].s[0]-'a';
         nd[i].end=nd[i].s[strlen(nd[i].s)-1]-'a';
         ++Out[nd[i].first];
         ++In[nd[i].end];
      } 
        
         int st = fun();
         //因为搜索的是字典序的第一个，所以将字符串从小到大排一下序！在搜索的时候按照升序搜索组合！ 
         sort(nd, nd+n, cmp);
         if(st==-1 || !dfs(st, 0))
            printf("***\n");
         else{
            printf("%s", nd[order[0]].s);
            for(int i=1; i<n; ++i)
               printf(".%s", nd[order[i]].s);
            printf("\n");
         } 
   }
   return 0;
}