1 /* 2 題意：打印歐拉回路！ 3 思路：開始時不明白，dfs為什么是后序遍歷？ 4 因為歐拉回路本身是一條回路，那么我們在dfs時，可能存在提前找到回路，這條回路可能不是歐拉回路， 5 因為沒有遍歷完成所有的邊！如果寫成前序遍歷的話，存儲起來的路徑就不是一條完整的路徑了！它有可能 6 是多條回路組成的！答案就是錯誤 的！如果是后序遍歷的話，當dfs是遇到了回路，那么就退出當前棧的搜索！ 7 去尋找其他的路徑！最終得到的只有一條回路路徑！-->歐拉回路~！ 8 */ 9 #include<iostream> 10 #include<cstring> 11 #define M 55 12 #define Max 0x3f3f3f3f 13 using namespace std; 14 15 int cnt[M][M]; 16 int deg[M]; 17 int map[M][M]; 18 int x; 19 20 struct Point{ 21 int x, y; 22 Point(){} 23 24 Point(int x, int y){ 25 this->x=x; 26 this->y=y; 27 } 28 }; 29 30 Point p[1005]; 31 int top; 32 33 void dfs(int u){ 34 if(!deg[u]) return; 35 for(int i=1; i<=50; ++i) 36 if(map[u][i] && cnt[u][i]){ 37 --cnt[u][i]; 38 --cnt[i][u]; 39 --deg[u]; 40 --deg[i]; 41 dfs(i); 42 p[++top]=Point(u, i); 43 } 44 } 45 46 int main(){ 47 int t, n, k=0; 48 cin>>t; 49 while(t--){ 50 cin>>n; 51 x=Max; 52 memset(cnt, 0, sizeof(cnt)); 53 memset(map, 0, sizeof(map)); 54 memset(deg, 0, sizeof(deg)); 55 for(int i=1; i<=n; ++i){ 56 int u, v; 57 cin>>u>>v; 58 deg[u]++; 59 deg[v]++; 60 map[u][v]=1; 61 map[v][u]=1; 62 cnt[u][v]++; 63 cnt[v][u]++; 64 if(x>u) x=u; 65 if(x>v) x=v; 66 } 67 int ok=0; 68 for(int i=1; i<=50; ++i) 69 if(deg[i]%2!=0){ 70 ok=1; 71 break; 72 } 73 cout<<"Case #"<<++k<<endl; 74 if(ok){ 75 cout<<"some beads may be lost"<<endl; 76 if(t) cout<<endl; 77 continue; 78 } 79 top=0; 80 dfs(x); 81 if(top==n){ 82 for(top; top>=1; --top) 83 cout<<p[top].x<<" "<<p[top].y<<endl; 84 } 85 else cout<<"some beads may be lost"<<endl; 86 if(t) cout<<endl; 87 } 88 return 0; 89 }

?

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

總結

以上是生活随笔為你收集整理的Uvaoj10054 - The Necklace的全部內容，希望文章能夠幫你解決所遇到的問題。

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