点击打开链接

无向图求欧拉回路：

1、图连通

2、所有顶点的度数位偶数

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; const int mt = 2000; const int ms = 50; bool vis[mt+5]; int g[ms][mt+5]; int deg[ms+5]; int f[ms+5]; stack
       
         s; int street, startv; int findset(int x){ return f[x]==x?f[x]:f[x]=findset(f[x]); } void Union(int x, int y){ int fx = findset(x); int fy = findset(y); if(fx!=fy){ f[fx] = fy; } } bool used[ms]; bool check(){ for(int i=1,cnt=0; i<=ms; ++i) if(used[i]){ if(deg[i]&1) return false; if(f[i]==i){ if(cnt++==1) return false; } } return true; } void euler(int u){ for(int i=1; i<=street; ++i) if(g[u][i]){ if(!vis[i]){ vis[i] = 1; euler(g[u][i]); s.push(i); } } } //ps:其实给出的图已经连通。。。。 int main() { int x, y, z; while(~scanf("%d%d", &x, &y)){ if(x==0&&y==0) break; scanf("%d", &z); memset(g, 0, sizeof g ); for(int i=0; i<=ms; ++i) f[i] = i; memset(used, 0, sizeof used ); memset(deg, 0, sizeof deg ); street = z; startv = min(x, y); deg[x]++; deg[y]++; g[x][z] = y; g[y][z] = x; Union(x, y); used[x] = used[y] = 1; while(~scanf("%d%d", &x, &y)){ if(x==0&&y==0) break; scanf("%d", &z); street = max(z, street); deg[x]++; deg[y]++; g[x][z] = y; g[y][z] = x; Union(x, y); used[x] = used[y] = 1; } if(!check()){ puts("Round trip does not exist."); continue; } else { memset(vis, 0, sizeof vis ); euler(startv); while(!s.empty()){ printf("%d ", s.top()); s.pop(); } printf("\n"); } } return 0; }