UVA 10054 无向图的欧拉回路输出路径

无向图其实跟有向图的做法是一样的，一直以为是不一样的，要好好深入学习一下。

输出路径方法：dfs，而且用一个栈保存经过的边，然后把栈的边逆顺序输出就是欧拉回路。

#include <cstdio>#include <cstring>#include <algorithm>#include <vector>using namespace std;struct edge {int v, vis, next;} edge[1004 << 1];int head[55], E;void init() {memset(head, -1, sizeof(head));E = 0;}void add(int s, int t) {edge[E].v = t;edge[E].vis = 0;edge[E].next = head[s];head[s] = E++;edge[E].v = s;edge[E].vis = 0;edge[E].next = head[t];head[t] = E++;}int n, d[55];void dfs(int u) {int i;for (i = head[u]; ~i; i = edge[i].next) {if (!edge[i].vis) {edge[i].vis = edge[i ^ 1].vis = 1;dfs(edge[i].v);printf("%d %d\n", edge[i].v, u);}}}int main() {int i, cas, ca = 1;scanf("%d", &cas);while (cas--) {scanf("%d", &n);init();int x, y, sta;for (i = 1; i <= 50; i++)d[i] = 0;while (n--) {scanf("%d%d", &x, &y);add(x, y);d[x]++;d[y]++;sta = x;}printf("Case #%d\n", ca++);for (i = 1; i <= 50; i++)if (d[i] & 1) {printf("some beads may be lost\n");break;}if (i > 50)dfs(sta);puts("");}return 0;}