本文主要是介绍百题纪念之1041 John's trip（欧拉回路），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目大意：
John拥有一辆新车，他想去拜访在同一个小镇上的朋友，但是他的朋友有很多且在每一条街上都有他的朋友，现在给出这些街道的信息x,y,z，（x，y是连接第z条街道的两个连接点），如果John能够不重复的经过每一条街道，如果不能，输出”Round trip does not exist.“，否则输出经过的街道的编号（按字典序最小输出）。
解题思路：
典型的求欧拉回路的方法，难点不在欧拉回路上，而是在如果记录街道信息上，两个连接点之间可以有多条街道。G[u][z]=v,表示街道z 的一端是u，那么另一端是v。
代码：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int nPoint, nRoad, start,top;
int G[2010][2010], vis[2010], degree[2010],que[2010];int qmax(int a, int b){return a > b ? a : b;
}int qmin(int a, int b){return a < b ? a : b;
}
void init(){nPoint = 0;nRoad = 0;start = 2000;memset(G, 0, sizeof(G));memset(vis, 0, sizeof(vis));memset(degree, 0, sizeof(degree));
}
void euler(int u){for(int v=1; v<=nRoad; v++){if(!vis[v] && G[u][v]){vis[v] = 1;euler(G[u][v]);que[top++] = v;}}
}
void work(){//printf("hello world\n");int flag = 0;for(int i=1; i<nPoint; i++){if(degree[i]%2 == 1){flag = 1;break;}}if(flag==1){printf("Round trip does not exist.\n");}else{top = 0;euler(start);//printf("top=%d\n", top);//printf("%d %d %d\n",nRoad, nPoint, start);for(int i=top-1; i>=0; i--){printf("%d",que[i]);if(i>0) printf(" ");}printf("\n");}
}
int main(){int x,y,z;int first=0;while(~scanf("%d%d", &x, &y)){if(x==0 && y==0 && first==0){break;}init();first = 1;scanf("%d", &z);G[x][z] = y;G[y][z] = x;degree[x]++;degree[y]++;start = qmin(start, qmin(x, y));nRoad = qmax(nRoad, z);nPoint = qmax(nPoint, qmax(x, y));while(scanf("%d%d", &x, &y)){if(x==0 && y==0){work();first=0;break;}scanf("%d", &z);G[x][z] = y;G[y][z] = x;degree[x]++;degree[y]++;start = qmin(start, qmin(x, y));nRoad = qmax(nRoad, z);nPoint = qmax(nPoint, qmax(x, y));}}return 0;
}这篇关于百题纪念之1041 John's trip（欧拉回路）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
