NYOJ-99 单词拼接（欧拉+回溯）
生活随笔
收集整理的這篇文章主要介紹了
NYOJ-99 单词拼接（欧拉+回溯）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
單詞拼接
時間限制：3000?ms ?|? 內存限制：65535?KB 難度：5 描述給你一些單詞，請你判斷能否把它們首尾串起來串成一串。
前一個單詞的結尾應該與下一個單詞的道字母相同。
如
?
aloha
dog
arachnid
gopher
tiger
rat
?
可以拼接成：aloha.arachnid.dog.gopher.rat.tiger
?
每組測試數據的第一行是一個整數M,表示該組測試數據中有M(2<M<1000)個互不相同的單詞，隨后的M行，每行是一個長度不超過30的單詞,單詞全部由小寫字母組成。
如果不存在拼接方案，則輸出
***
解析：
有向圖G 為歐拉回路:
當且僅當G 的基圖連通，且所有頂點的入度等于出度。
有向圖G 為歐拉路:
當且僅當G 的基圖連通，且只存在一個頂點u 的入度比出度大1、
只存在一個頂點v 的入度比出度小1，其它所有頂點的入度等于出度。本題還有要注意的一點就是：
單詞的首字母應該看做是出度，尾字母看做是入度
代碼一：----TLE
我先用并查集判斷是否連通，然后再據歐拉路的條件判斷是否能形成歐拉路，
最后才搜索字典序最小，超時也不足為奇，不過為此我也糾結了好幾天，后來想了想可以不用使用并查集判斷連通，可以再最后的搜索中邊搜索邊判斷是否連通
?
View Code 1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <iostream> 5 #include <algorithm> 6 7 using namespace std; 8 9 const int M = 1005; 10 struct word 11 { 12 char s[35]; 13 int start; 14 int end; 15 }str[M]; 16 int in_degree[26], out_degree[26]; // 分別記錄入度和出度 17 int father[26]; // 并查集中的數組 18 bool use[26]; //記錄首尾出現的字母，用并查集時即判斷出現過的字母是否連通 19 bool visit[M]; // 搜索路徑時候回溯時候用的 20 int ans[M]; // 結果序列 21 int n, flagOfStart; 22 /*要判斷存在歐拉路徑后輸出字典序最小的路徑， 23 先把單詞按字典序排序，然后判斷是歐拉回路還是只是歐拉通路， 24 如果是歐拉回路，直接從第0號單詞開始搜，否則，找到出度比入度大1的 25 那個單詞開始搜標記為歐拉路起點的字母，flagOfStart即記錄起點編號； 26 27 28 int find_father(int i) 29 { 30 if(father[i] == -1) 31 return i; 32 else 33 return find_father(father[i]); 34 } 35 36 void merge(int num1, int num2) 37 { 38 num1 = find_father(num1); 39 num2 = find_father(num2); 40 if(num1 != num2) 41 father[num1] = num2; 42 } 43 44 void init() 45 { 46 memset(in_degree, 0, sizeof(in_degree)); 47 memset(out_degree, 0, sizeof(out_degree)); 48 memset(father, -1, sizeof(father)); 49 memset(visit, false, sizeof(visit)); 50 memset(use, false, sizeof(use)); 51 scanf("%d", &n); 52 for(int i = 0; i < n; ++i) 53 { 54 scanf("%s", str[i].s); 55 int len = strlen(str[i].s); 56 str[i].start = str[i].s[0] - 'a'; 57 str[i].end = str[i].s[len-1] - 'a'; 58 use[str[i].start] = use[str[i].end] = true; 59 merge(str[i].start, str[i].end); 60 ++out_degree[str[i].start]; 61 ++in_degree[str[i].end]; 62 } 63 } 64 65 bool judge() 66 { 67 flagOfStart = 0; 68 int cnt_in = 0; 69 int cnt_out = 0; 70 int tmp = 0; 71 for(int i = 0; i < 26; ++i) //并查集判斷是否連通 72 { 73 if(use[i] && father[i] == -1) 74 { 75 ++tmp; 76 if(tmp > 1) // 不連通 77 return false; 78 } 79 } 80 for(int i = 0; i < 26; ++i) // 判斷是否能形成歐拉路或歐拉回路 81 { 82 if(!use[i]) 83 continue; 84 if(abs(in_degree[i] - out_degree[i]) >= 2) 85 return false; 86 87 // 下邊這點我把起點弄錯了，害我調試了半天(我把出度和入度理解反了) 88 if(in_degree[i] - out_degree[i] == 1) //入度比出度大一，若為歐拉路則為唯一的終點 89 ++cnt_in; 90 else if(in_degree[i] - out_degree[i] == -1)//入度比出度小一，若為歐拉路則為唯一的起點 91 { 92 ++cnt_out; 93 flagOfStart = i; // 若是歐拉路，則i必然是起點 94 } 95 } 96 if(!flagOfStart) // 如果是歐拉回路，則找到任意第一個出現過的字母作為搜索的起點即可 97 { 98 for(int i = 0; i < 26; ++i) 99 if(use[i]) 100 { 101 flagOfStart = i; 102 break; 103 } 104 } 105 if(cnt_out == 0 && cnt_in ==0 || cnt_out == 1 && cnt_in == 1) 106 return true; 107 return false; 108 } 109 110 bool cmp(word p, word q) 111 { 112 return strcmp(p.s, q.s) < 0; 113 } 114 115 void DFS(int cur) // 在進行DFS的時候已經確定了本題的答案一定存在， 116 { //只是找到字典序最小的那組序列即可 117 if(cur == n) 118 { 119 for(int i = 0; i < n-1; ++i) 120 printf("%s.", str[ans[i]].s); 121 printf("%s\n", str[ans[n-1]].s); 122 return; 123 } 124 for(int i = 0; i < n; ++i) 125 { 126 if(str[i].start < flagOfStart || visit[i]) 127 continue; 128 if(str[i].start > flagOfStart) 129 return; 130 ans[cur] = i; 131 visit[i] = true; 132 flagOfStart = str[i].end; 133 DFS(cur+1); 134 visit[i] = false; 135 } 136 } 137 138 int main() 139 { 140 int T; 141 scanf("%d", &T); 142 while(T--) 143 { 144 init(); 145 if(!judge()) 146 { 147 printf("***\n"); 148 continue; 149 } 150 sort(str, str + n, cmp); 151 DFS(0); 152 } 153 return 0; 154 }?
代碼二： -----沒用并查集，還是超時fuck。。。。。
View Code 1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <iostream> 5 #include <algorithm> 6 7 using namespace std; 8 9 const int M = 1005; 10 struct word 11 { 12 char s[35]; 13 int start; 14 int end; 15 }str[M]; 16 int in_degree[26], out_degree[26]; 17 bool use[26]; 18 bool visit[M]; 19 int ans[M]; 20 int n, flagOfStart; 21 22 void init() 23 { 24 memset(in_degree, 0, sizeof(in_degree)); 25 memset(out_degree, 0, sizeof(out_degree)); 26 memset(visit, false, sizeof(visit)); 27 memset(use, false, sizeof(use)); 28 scanf("%d", &n); 29 for(int i = 0; i < n; ++i) 30 { 31 scanf("%s", str[i].s); 32 int len = strlen(str[i].s); 33 str[i].start = str[i].s[0] - 'a'; 34 str[i].end = str[i].s[len-1] - 'a'; 35 use[str[i].start] = use[str[i].end] = true; 36 ++out_degree[str[i].start]; 37 ++in_degree[str[i].end]; 38 } 39 } 40 41 bool judge() 42 { 43 flagOfStart = 0; 44 int cnt_in = 0; 45 int cnt_out = 0; 46 int tmp = 0; 47 for(int i = 0; i < 26; ++i) 48 { 49 if(!use[i]) 50 continue; 51 if(abs(in_degree[i] - out_degree[i]) >= 2) 52 return false; 53 if(in_degree[i] - out_degree[i] == 1) //入度比出度大一，若為歐拉路則為唯一的終點 54 ++cnt_in; 55 else if(in_degree[i] - out_degree[i] == -1)//入度比出度小一，若為歐拉路則為唯一的起點 56 { 57 ++cnt_out; 58 flagOfStart = i; // 若是歐拉路，則i必然是起點 59 } 60 } 61 if(!flagOfStart) // 如果是歐拉回路，則找到任意第一個出現過的字母作為搜索的起點即可 62 { 63 for(int i = 0; i < 26; ++i) 64 if(use[i]) 65 { 66 flagOfStart = i; 67 break; 68 } 69 } 70 if(cnt_out == 0 && cnt_in ==0 || cnt_out == 1 && cnt_in == 1) 71 return true; 72 return false; 73 } 74 75 bool cmp(word p, word q) 76 { 77 return strcmp(p.s, q.s) < 0; 78 } 79 80 bool DFS(int cur) 81 { 82 if(cur == n) 83 { 84 return true; 85 } 86 for(int i = 0; i < n; ++i) 87 { 88 if(str[i].start < flagOfStart || visit[i]) 89 continue; 90 if(str[i].start > flagOfStart) 91 return false; 92 ans[cur] = i; 93 visit[i] = true; 94 flagOfStart = str[i].end; 95 if(DFS(cur+1)) 96 return true; 97 visit[i] = false; 98 } 99 return false; 100 } 101 102 int main() 103 { 104 int T; 105 scanf("%d", &T); 106 while(T--) 107 { 108 init(); 109 if(!judge()) 110 { 111 112 } 113 sort(str, str + n, cmp); 114 if(!DFS(0)) 115 { 116 printf("***\n"); 117 continue; 118 } 119 for(int i = 0; i < n-1; ++i) 120 printf("%s.", str[ans[i]].s); 121 printf("%s\n", str[ans[n-1]].s); 122 } 123 return 0; 124 }代碼三：----AC，哥桑心了
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 using namespace std; 5 struct node 6 { 7 char s[31]; 8 int first,last; 9 }; 10 11 node a[1001]; 12 int degree_in[1001],degree_out[1001],m,order[1001]; 13 bool used[1001]; 14 15 int f() 16 { 17 int x1,x2,ans=0,i; 18 x1=x2=0; 19 for(i=0;i<26;++i) 20 { 21 if(abs(degree_in[i]-degree_out[i])>=2) 22 return -1; 23 else if(degree_in[i]-degree_out[i]==1) 24 x1++; 25 else if(degree_in[i]-degree_out[i]==-1) 26 { 27 x2++; 28 ans=i; 29 } 30 } 31 if(x1>1||x2>1) //當時三個度時，必定是 12 和21，相同的不能大于等于2，不然不能構成歐拉回路 32 return -1; 33 else if(x1==0) 34 { 35 for(i=0;i<26;++i) 36 if(degree_out[i]) 37 return i; //找到一個就行 38 } 39 else 40 return ans; 41 42 } 43 bool cmp(node a,node b) 44 { 45 return strcmp(a.s,b.s)<0; 46 } 47 48 bool dfs(int st,int cnt) 49 { 50 int i; 51 if(cnt==m) 52 return 1; 53 for(i=0;i<m;++i) 54 { 55 if(a[i].first<st||used[i]) 56 continue; 57 else if(a[i].first>st) 58 return false; 59 used[i]=true; 60 order[cnt]=i; 61 if(dfs(a[i].last,cnt+1)) 62 return 1; 63 used[i]=false;//回溯判斷是否形成歐拉路徑 64 } 65 return false; 66 } 67 68 69 int main() 70 { 71 int N,len,i,start; 72 scanf("%d",&N); 73 while(N--) 74 { 75 memset(used,false,sizeof(used)); 76 memset(degree_out,0,sizeof(degree_out)); 77 memset(degree_in,0,sizeof(degree_in)); 78 scanf("%d",&m); 79 for(i=0;i<m;++i) 80 { 81 scanf("%s",a[i].s); 82 len = strlen(a[i].s); 83 a[i].first =a[i].s[0]-'a'; 84 a[i].last =a[i].s[len-1]-'a'; 85 degree_out[a[i].s[0]-'a']++; 86 degree_in[a[i].s[len-1]-'a']++;//注意這里的入肚出度 87 } 88 start=f(); 89 if(start ==-1) 90 { 91 printf("***\n"); 92 continue; 93 } 94 sort(a,a+m,cmp); 95 if(!dfs(start,0)) 96 { 97 printf("***\n"); 98 continue; 99 } 100 printf("%s",a[order[0]].s); 101 for(i=1;i<m;i++) 102 printf(".%s",a[order[i]].s); 103 printf("\n"); 104 } 105 return 0; 106 }?
?
總結
以上是生活随笔為你收集整理的NYOJ-99 单词拼接（欧拉+回溯）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 求1/2+1/4+...+1/n
- 下一篇： Unix平台上OUI启动常见问题