NYOJ 99單詞拼接（有向圖的歐拉（回）路）

  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 }

轉載于:https://www.cnblogs.com/hujunzheng/p/3900428.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/531777.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/531777.shtml
英文地址，請注明出處：http://en.pswp.cn/news/531777.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！