本文链接:http://www.cnblogs.com/Ash-ly/p/5398549.html
题意：
Johnny 有了一台新车，他想去访问他所有的朋友(赤裸裸的炫耀？),他的朋友有很多，住在城市中的街道上，于是他就开始规划自己的路了，在这个城市中有很多街道，他想找一个路径，这个路径经过一个街道仅一次，但能访问完他所有的朋友，他从他父母家出发，并且回来时也必须在他父母家。
在这个城市中，一共有N(N < 1995)个街道，共有M(M <= 44)个转折点，转折点就是一个街道的两端，每条街道和转折点的编号都不同。如果在一个转折点有多种选择，他会优先选择街道编号比较小的。
让你帮忙写一个程序，找到这个路径，如果找不到就打印“Round trip does not exist.”，从 1 号转折点出发，最后必须回到 1 号转折点，经过每条街道仅一次，访问完他所有的朋友，街道是双向的，但是不能掉头。
思路：
把城市想象成一个图，转折点即是点，街道即是边，从某一起点出发，访问所有边且每条边仅访问一次，再回到起点，很自然想到欧拉回路。首先需要判断是否存在欧拉回路，无向图的每个点的入度为偶数就一定存在欧拉回路。然后由于是无向图，在存储边的时候需要正反各储存一次，访问一条边，也要同时删除两条边，正反各一条。题目还有求输出字典序最小的，这里可以在选择边的时候每次选择编号最小的那个遍历，然后回溯回来时，也是最短的。
代码：
/* POJ 1041 algs:链式前向星(存图) + 欧拉回路(找图) time:2016/4/25 */ #include <stdio.h> #include <string.h> #include <iostream> #include <math.h> #include <queue> #include <stack> #include <algorithm> using namespace std; int V,E; const int maxV = 44; const int maxE = 1995; int head[maxV + 7]; int visit[2 * maxE + 7]; //标志边是否被访问 int degree[maxV + 7]; //每个点的度 struct EdgeNode { int to; int w; //题目所给边的编号 int next; }edges[2 * maxE + 7]; int Max(int x, int y, int z){ return ( x > y ? (x > z ? x : z) : (y > z ? y : z) ) ; } int isEulur() //是否是欧拉回路 无向图不含有度数为奇数的点 { for(int i = 1; i <= V; i++) if(degree[i] & 1) return 0; return 1; } void debugio(); void debugG(); void debugvi(); stack<int> ansE;//用一个栈来存放答案 void eulurDFS(int now) { for(int i = 1; i <= degree[now]; i++) //每个点可选择下一个扩展节点的个数 { int min = maxE + 7; //用于找到编号最小边 int tmpvst = head[now]; //编号最小边的下标 for(int k = head[now]; k != -1; k = edges[k].next)//在所有相邻的边中找编号最小边 { if(!visit[k] && edges[k].w < min) min = edges[k].w, tmpvst = k; } if(visit[tmpvst] || min == maxE + 7) continue; visit[tmpvst] = 1; //标志找到的边为已访问,在链式前向星中每条边被存储了两次 tmpvst & 1 ? visit[tmpvst + 1] = 1 : visit[tmpvst - 1] = 1; --degree[now],--degree[edges[tmpvst].to]; //访问一条边,则这条边两端点的度数各减一、否则TLE！！ eulurDFS(edges[tmpvst].to);//访问编号最小边 ansE.push(tmpvst); //回溯的过程中记录答案 } } int main() { //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); while(true) { int x, y; scanf("%d%d", &x, &y); if(!(x || y)) break; E = 0; V = 0; memset(&edges, 0, sizeof(EdgeNode)); memset(head, -1, sizeof(head)); memset(degree, 0, sizeof(degree)); while(x || y) { int z; scanf("%d", &z); ++E; edges[2 * E - 1].to = y; //无向图每条边储存两次 edges[2 * E - 1].w = z; edges[2 * E - 1].next = head[x]; head[x] = 2 * E - 1; edges[2 * E].to = x; edges[2 * E].w = z; edges[2 * E].next = head[y]; head[y] = 2 * E; degree[x]++; //度数 degree[y]++; V = Max(V, x, y); scanf("%d%d", &x, &y); } if(isEulur()) { memset(visit, 0, sizeof(visit)); eulurDFS(1); int pe = 0; while(!ansE.empty()) { printf( pe++ ?" %d":"%d", edges[ansE.top()].w); ansE.pop(); } printf(" "); } else //不存在欧拉回路 printf("Round trip does not exist. "); } return 0; }