寒鸽儿のBlog

偶数度数 --> 欧拉回路
两个奇数度数 --> 普通欧拉回路

利用栈的性质处理一点多环的情况。
注意一定是在回溯时入栈。
在外部逆序输出栈内元素即可。

#include <cstdio>
#include <cstring>

using namespace std;

const int N = 1234, M = 5678;
int head[N], ver[M<<1], nex[M<<1], vis[M<<1], tot;
inline void addedge(int u, int v) {
	ver[tot] = v; nex[tot] = head[u]; head[u] = tot++;
}

int sta[N*M], top;
void dfsE(int cur) {
	for(int i = head[cur]; ~i; i = nex[i]) 
		if(!vis[i]) {
			vis[i] = vis[i^1] = 1;
			dfsE(ver[i]);
			sta[top++] = ver[i];
		}
}

int main() {
	memset(head, -1, sizeof(head));
	int n, m, u, v;
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; ++i) {
		scanf("%d %d", &u, &v);
		addedge(u, v);
		addedge(v, u);
	}
	dfsE(1);
	while(top) {
		printf("%d ", sta[--top]);
	}
    printf("1\n");
	return 0;
}