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

總結

以上是生活随笔為你收集整理的NYOJ 99单词拼接（有向图的欧拉（回）路）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。