POJ 2230 Watchcow：无向图欧拉回路 Hierholzer 算法

题目大意

给定无向图，求从节点 1 出发的欧拉回路（每条边恰好经过一次，回到起点）。输出路径节点序列。

算法：Hierholzer（非递归/递归均可）

1. 从起点 DFS，沿未访问边深入
2. 无路可走时回溯，将节点加入答案序列
3. 最终逆序得到欧拉回路

关键实现细节

• 边标记：无向图每条边存两个有向边，共用 id，访问时标记 vis[id]=1
• 邻接表优化：DFS 中动态更新 head[u] 跳过已访问边，避免重复扫描
• 递归深度：边数 ≤ 10000，递归安全

C++ 实现

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int MAXE = 120000;
const int MAXV = 11000;

struct Edge { int v, id, next; } edge[MAXE];
int head[MAXV], cnt, vis[MAXE], path[MAXE], tot;

void addEdge(int u, int v, int id) {
    edge[cnt] = {v, id, head[u]};
    head[u] = cnt++;
}

void dfs(int u) {
    for (int &i = head[u]; i != -1; i = edge[i].next) {
        if (!vis[edge[i].id]) {
            vis[edge[i].id] = 1;
            int v = edge[i].v;
            dfs(v);
        }
    }
    path[tot++] = u;
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) == 2) {
        memset(head, -1, sizeof(head));
        cnt = tot = 0;
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < m; ++i) {
            int u, v; scanf("%d%d", &u, &v);
            addEdge(u, v, i<<1);
            addEdge(v, u, i<<1|1);
        }
        dfs(1);
        for (int i = tot-1; i >= 0; --i)
            printf("%d\n", path[i]);
    }
    return 0;
}

复杂度

• 时间：O(V + E)
• 空间：O(V + E)

欧拉回路存在条件（无向图）

1. 图连通（非零度节点在同一连通分量）
2. 所有节点度数为偶数

本题保证有解，无需预检查。