[hihocoder 1181 欧拉路 二] Fleury 算法求欧拉回路

题目链接： [hihocoder 1181 欧拉路 二]  #include <set> #include <stack> #include <queue> #include <cmath> #include <cstdio> #include <string> #include <cstring> #include <iostream> #include <algorithm> using namespace std; //#pragma comment(linker, "/STACK:1024000000,1024000000") #define FIN freopen("input.txt","r",stdin) #define FOUT freopen("output.txt","w",stdout) #define fst first #define snd second //typedef __int64 LL; typedef long long LL; typedef pair<int, int> PII; const int MAXN = 1e4 + 5; const int MAXE = 5e4 + 5; int T, N, M, K; struct Edge { int v, next; Edge() {} Edge (int v, int next) : v (v), next (next) {} } edges[MAXE << 1]; int head[MAXN], tot; int path[MAXN], cnt; int deg[MAXN]; bool used[MAXE]; void init() { tot = 0; cnt = 0; memset (head, -1, sizeof (head) ); memset (deg, 0, sizeof (deg) ); memset (used, false, sizeof (used) ); } void add_edge (int u, int v) { edges[tot] = Edge (v, head[u]); head[u] = tot++; } void dfs (int u) { int v; // 删边遍历 for (int i = head[u]; ~i; i = head[u]) { v = edges[i].v; head[u] = edges[i].next; if (!used[i]) { used[i] = used[i ^ 1] = true; dfs (v); } } path[++ cnt] = u; } int main() { #ifdef __WONZY_LOCAL__ FIN; #endif // __WONZY_LOCAL__ int u, v, x; while (~scanf ("%d %d", &N, &M) ) { init(); for (int i = 1; i <= M; i++) { scanf ("%d %d", &u, &v); add_edge (u, v); add_edge (v, u); deg[u] ++; deg[v] ++; } int s = -1, t = -1, num = 0; for (int i = 1; i <= N; i++) { if (deg[i] & 1) { num ++; if (num == 1) s = i; else t = i; } } if (num == 0) s = 1; dfs (s); for (int i = 1; i <= M + 1; i++) { printf ("%d%c", path[i], i <= M ? ' ' : '\n'); } } return 0; }