1 /* 2     题意：打印欧拉回路！ 3     思路：开始时不明白，dfs为什么是后序遍历？  4     因为欧拉回路本身是一条回路，那么我们在dfs时，可能存在提前找到回路，这条回路可能不是欧拉回路， 5     因为没有遍历完成所有的边！如果写成前序遍历的话，存储起来的路径就不是一条完整的路径了！它有可能 6     是多条回路组成的！答案就是错误 的！如果是后序遍历的话，当dfs是遇到了回路，那么就退出当前栈的搜索！ 7     去寻找其他的路径！最终得到的只有一条回路路径！-->欧拉回路~！  8 */  9 #include<iostream>10 #include<cstring>11 #define M 5512 #define Max 0x3f3f3f3f13 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 }