欧拉路与欧拉回路

代码模板

欧拉路与欧拉回路的判定与构造：Hierholzer 算法的原理与实现。

  • 欧拉路
  • 图论
  • Hierholzer

一句话算法

欧拉路是一笔走完所有边的路径；先用连通性和度数判定是否存在，再用 Hierholzer 算法“走到无路可走再回溯收路”，就能线性构造答案。

问题模型

给定一张图，要求找出一条路径，使得：

  • 每条边恰好经过一次。
  • 顶点可以重复经过。
  • 如果起点和终点相同，称为欧拉回路。
  • 如果起点和终点可以不同，称为欧拉路。

欧拉路问题起源于柯尼斯堡七桥问题：能不能从某处出发，每座桥恰好走一次？

本文讨论两类竞赛中最常用的模型：

  • 无向图欧拉路/回路。
  • 有向图欧拉路/回路。

无向图存在条件

忽略度数为 00 的孤立点后，所有有边的顶点必须连通。

在此基础上：

  • 奇度顶点个数为 00：存在欧拉回路。
  • 奇度顶点个数为 22：存在欧拉路，起点和终点就是这两个奇度顶点。
  • 其他情况：不存在欧拉路。

三种情况一图看懂：三角形每个点度数都是 22，存在欧拉回路；三个点的链恰有两个奇度点，存在欧拉路；中心点连三条边的星形有 44 个奇度点，无解。

无向图奇度点判定示意：奇度点 0 个时存在欧拉回路，2 个时存在欧拉路，4 个时无解，奇度顶点用橙色描边并标注奇字

有向图存在条件

忽略入度和出度都为 00 的孤立点后，所有有边的顶点在弱连通意义下连通。也就是把有向边当成无向边后连通。

在此基础上：

  • 所有点满足 in(v)=out(v)in(v)=out(v)：存在有向欧拉回路。
  • 恰有一个点满足 out(s)=in(s)+1out(s)=in(s)+1，恰有一个点满足 in(t)=out(t)+1in(t)=out(t)+1，其他点满足 in(v)=out(v)in(v)=out(v)：存在从 ss 到 tt 的有向欧拉路。
  • 其他情况：不存在有向欧拉路。

核心直觉

欧拉路的关键不是“能不能乱走”，而是“每条边只能用一次，最后还能把所有边接成一条连续路径”。

Hierholzer 算法的直觉是：图里的欧拉回路可以看成很多小环套在一起。普通 DFS 如果进门就记录路径，可能先走完一个小环，然后主干上的边还没有接进去。Hierholzer 反过来做：走边时先不急着输出，等一个点已经没有未走的边时，再把它放进答案。

这个“回溯时加入答案”的动作，本质是在把最里面的小环先收好，再一层一层拼回主路径。

可以把它理解成：

  • 前序记录：边走边写，遇到分叉时容易把后面的环插不回去。
  • 后序记录：先把分叉里的边全部走完，回溯时自然完成拼接。

因此 Hierholzer 的答案通常是逆序产生的，最后 reverse 一次即可。

下图演示这个过程：从 11 走到 22 后钻进小环 2→3→4→22 \to 3 \to 4 \to 2 先走完，再沿 2→52 \to 5 离开；回溯时按 5,2,4,3,2,15, 2, 4, 3, 2, 1 的顺序收集顶点，反转后就是答案 1,2,3,4,2,51, 2, 3, 4, 2, 5。

Hierholzer 算法示意图：编号 1 到 5 是走边顺序，橙色小环先走完，底部展示回溯收集顺序 5 2 4 3 2 1，反转得到答案 1 2 3 4 2 5

算法步骤

无向图：

  1. 建邻接表，每条无向边分两次加入邻接表，但共享同一个边编号 id。
  2. 统计每个点的度数，找一个有边的点作为连通性检查起点。
  3. 忽略孤立点检查连通性。
  4. 统计奇度顶点个数：
    • 若为 22，从任意一个奇度点出发。
    • 若为 00，从任意有边的点出发。
    • 否则无解。
  5. 用栈模拟 Hierholzer：
    • 当前点还有未使用边，就标记这条边并走到下一点。
    • 当前点没有未使用边，就把它加入 path 并弹栈。
  6. 若最终 path.size() != m+1，说明没有覆盖所有边，无解。
  7. 反转 path，得到欧拉路或欧拉回路的顶点序列。

有向图：

  1. 建有向邻接表，同时建一张弱连通检查用的无向图。
  2. 统计每个点的入度 indeg 和出度 outdeg。
  3. 忽略孤立点检查弱连通性。
  4. 根据入度、出度差确定起点：
    • 回路：所有点入度等于出度，从任意有边点出发。
    • 路径：从唯一满足 outdeg = indeg + 1 的点出发。
  5. 后续 Hierholzer 过程与无向图相同，只是边只沿原方向走。

算法证明

先证明判定条件。

无向图中，一条欧拉路经过中间点时，每进入一次就必须离开一次，所以中间点贡献成对的边，度数为偶数。只有起点和终点可以多一次“离开”或“进入”，所以最多有两个奇度点。若是回路，起点也会回到自身，所有点度数都为偶数。

有向图同理：中间点每进入一次就必须离开一次，所以 in(v)=out(v)in(v)=out(v)。路径起点多一次离开，终点多一次进入，因此起点满足 out=in+1out=in+1，终点满足 in=out+1in=out+1。

再证明构造正确。

Hierholzer 始终维护一个不变量：已经标记使用的边不会再被使用，当前栈表示一条由已使用边组成的连续行走轨迹。

当一个顶点没有未使用边时，把它放入答案是安全的，因为以后不可能再从这个点接出新的未使用边；它在最终欧拉路中的后续部分已经确定。回溯不断重复这个过程，相当于先完成局部小环，再把小环接回主路径。

若图满足存在条件，所有有边顶点在同一个连通块中，并且度数平衡保证路径不会在错误的位置提前断掉。算法每次恰好消耗一条未使用边，所以最终若得到 m+1m+1 个顶点，就对应恰好使用了全部 mm 条边的一条欧拉路。

复杂度分析

设顶点数为 nn，边数为 mm。

  • 建图时间复杂度：O(n+m)O(n+m)。
  • 连通性检查时间复杂度：O(n+m)O(n+m)。
  • Hierholzer 构造中，每条边只会被跳过或使用常数次，总时间复杂度为 O(n+m)O(n+m)。
  • 空间复杂度为 O(n+m)O(n+m)。

代码实现

无向图模板

C++
cpp 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199

        #include <bits/stdc++.h>
using namespace std;

// 无向图欧拉路 / 欧拉回路（Hierholzer 算法）
// 输入：
//   n m
//   m 行 u v
// 输出：
//   一条欧拉路（或欧拉回路）的顶点序列，不存在时输出 NO
//
// 代码分层：
//   1. 建图层：init / add_edge
//   2. 判定层：connected（连通性）+ check_degree（度数条件）
//   3. 构造层：hierholzer（算法本体，只管在有解时走出路径）
//   4. 入口层：solve（把判定和串起来）+ main（输入输出）
//
// 存在性条件（两个都要满足）：
//   1. 所有非孤立点连通；
//   2. 奇度数点个数为 0（欧拉回路）或 2（欧拉路，必须从奇度数点出发）。
// 时间复杂度 O(n + m)。

struct EulerPathUndirected {
    struct Edge {
        int to;
        int id; // 边的编号，用来标记这条边是否已经走过（重边靠编号区分）
    };

    int n = 0;
    int edge_cnt = 0; // 已加入的边数
    vector<vector<Edge>> g;
    vector<int> deg; // 每个点的度数

    void init(int _n) {
        n = _n;
        edge_cnt = 0;
        g.assign(n + 1, vector<Edge>());
        deg.assign(n + 1, 0);
    }

    // 加一条无向边 u - v。两个方向共用同一个 id。
    void add_edge(int u, int v) {
        ++edge_cnt;
        g[u].push_back({v, edge_cnt});
        g[v].push_back({u, edge_cnt});
        if (u == v) {
            deg[u] += 2; // 易错点：自环给度数贡献 2
        } else {
            ++deg[u];
            ++deg[v];
        }
    }

    // ---- 判定层 ----

    // 条件 1：所有非孤立点是否连通。
    // 孤立点不参与判断：它们既不影响欧拉路的存在性，也不会出现在路径里。
    bool connected() {
        // 找任意一个「有边相连」的点作为 DFS 起点
        int first = -1;
        for (int i = 1; i <= n; ++i) {
            if (deg[i] > 0) {
                first = i;
                break;
            }
        }
        // 边界：图中没有任何边，视为连通（此时欧拉路是空序列）
        if (first == -1) return true;

        // 迭代 DFS 检查连通性（递归写法在链状图上可能爆栈）。
        // 自环 u == v 时 g[u] 里有 {u, id}，vis 会直接跳过，不影响结果。
        vector<char> vis(n + 1, 0);
        stack<int> st;
        st.push(first);
        vis[first] = 1;
        while (!st.empty()) {
            int u = st.top();
            st.pop();
            for (const auto &e : g[u]) {
                if (!vis[e.to]) {
                    vis[e.to] = 1;
                    st.push(e.to);
                }
            }
        }

        for (int i = 1; i <= n; ++i) {
            if (deg[i] > 0 && !vis[i]) return false;
        }
        return true;
    }

    // 条件 2：奇度数点只能有 0 个或 2 个。
    // 有 2 个奇点时必须从奇点出发（欧拉路），全偶度时从任意有边的点出发（欧拉回路）。
    // 判定通过时 start 是合法起点。
    bool check_degree(int &start) {
        start = -1;
        for (int i = 1; i <= n; ++i) {
            if (deg[i] > 0) {
                start = i; // 回路情形的默认起点
                break;
            }
        }

        int odd_count = 0;
        for (int i = 1; i <= n; ++i) {
            if (deg[i] % 2 == 1) {
                ++odd_count;
                start = i; // 最后一个奇点；恰有 2 个奇点时任取一个作起点都合法
            }
        }
        return odd_count == 0 || odd_count == 2;
    }

    // ---- 构造层 ----

    // Hierholzer 算法本体：从 start 出发走出一条用完所有边的路径。
    // 前提：connected() 与 check_degree() 都已通过。
    // 返回顶点序列，正常时长度为边数 + 1。
    vector<int> hierholzer(int start) {
        vector<char> used(edge_cnt + 1, 0); // used[id]：第 id 条边是否已走
        // iter[u]：u 的「当前弧」，指向第一条还没走过的邻接边。
        // 走过的边不再扫描，保证每条边只被处理一次，总复杂度 O(n + m)。
        // 易错点：不要每次从 g[u][0] 重新扫，否则退化到 O(m^2)。
        // 无向边两个方向共用一个 id，标记一次就表示这条边整体已用，
        // 所以不会把同一条边来回走两遍。
        vector<int> iter(n + 1, 0), stack_path, path;
        stack_path.push_back(start);

        while (!stack_path.empty()) {
            int u = stack_path.back();
            // 跳过已经走过的边（重边可能出现连续多条已用边）
            while (iter[u] < (int)g[u].size() && used[g[u][iter[u]].id]) {
                ++iter[u];
            }

            if (iter[u] == (int)g[u].size()) {
                // u 的边走完了：u 是当前这条「死胡同」的端点，
                // 此时才把 u 记入 path（后序收集，最终 reverse 后才是正序）。
                path.push_back(u);
                stack_path.pop_back();
            } else {
                Edge e = g[u][iter[u]++]; // 取走这条边
                used[e.id] = 1;
                stack_path.push_back(e.to);
            }
        }

        // path 是「回溯顺序」收集的，reverse 后才是从起点到终点的欧拉路。
        reverse(path.begin(), path.end());
        return path;
    }

    // ---- 入口层 ----

    // 总入口：存在欧拉路/回路时把顶点序列写进 path 并返回 true。
    // 图中没有边时 path 是空序列，也视为有解。
    bool solve(vector<int> &path) {
        path.clear();
        int start = -1;
        if (!connected() || !check_degree(start)) return false;
        if (edge_cnt == 0) return true; // 边界：没有任何边，欧拉路是空序列

        path = hierholzer(start);
        // 理论上前面的判定已经保证有解，这里再兜底一次防御非法输入。
        if ((int)path.size() != edge_cnt + 1) {
            path.clear();
            return false;
        }
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    EulerPathUndirected solver;
    solver.init(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        solver.add_edge(u, v);
    }

    vector<int> path;
    if (!solver.solve(path)) {
        cout << "NO\n";
        return 0;
    }
    for (int i = 0; i < (int)path.size(); ++i) {
        if (i) cout << ' ';
        cout << path[i];
    }
    cout << '\n';
    return 0;
}
C++ 竞赛版

不用 struct 的精简写法：省去显式连通性检查，靠 path 长度兜底判定，适合比赛现场手写。

cpp 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

        #include <bits/stdc++.h>
using namespace std;

// 无向图欧拉路 / 欧拉回路竞赛精简版（Hierholzer，不用 struct）
// 输入 n m 与 m 条边，输出一条欧拉路的顶点序列，无解输出 NO
// 判定：奇度点只能有 0 个（回路）或 2 个（路，从奇点出发）
// 连通性不用单独判：走不完所有边（path 长度 != m+1）就是不连通
// 口诀：走不动了再记点，记完 reverse

int n, m;
vector<vector<pair<int, int>>> g; // 邻接表 {终点, 边编号}
vector<int> deg, used, cur, path; // used: 边已走；cur: 当前弧

void hierholzer(int s) {
    vector<int> st = {s};
    while (!st.empty()) {
        int u = st.back();
        // 跳过已走的边；cur 保证每条边只被扫过常数次，总复杂度 O(n+m)
        while (cur[u] < (int)g[u].size() && used[g[u][cur[u]].second]) cur[u]++;
        if (cur[u] == (int)g[u].size()) {
            path.push_back(u); // 走不动才记点（后序），reverse 后才是答案
            st.pop_back();
        } else {
            auto e = g[u][cur[u]++]; // 用掉这条边，走向下一点
            used[e.second] = 1;
            st.push_back(e.first);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    g.assign(n + 1, {});
    deg.assign(n + 1, 0);
    used.assign(m + 1, 0);
    cur.assign(n + 1, 0);
    for (int id = 1; id <= m; id++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back({v, id});
        g[v].push_back({u, id}); // 两个方向共用编号，不会来回走同一条边
        deg[u] += (u == v ? 2 : 1); // 易错点：自环度数 +2
        if (u != v) deg[v]++;
    }

    int s = -1, odd = 0;
    for (int i = 1; i <= n; i++) {
        if (deg[i] % 2) odd++, s = i; // 奇点只可能是端点
    }
    if (odd != 0 && odd != 2) {
        cout << "NO\n";
        return 0;
    }
    if (s == -1) { // 全偶度是回路，任取一个有边的点出发
        for (int i = 1; i <= n; i++)
            if (deg[i]) { s = i; break; }
    }
    if (s == -1) { // 边界：没有任何边，欧拉路是空序列
        cout << '\n';
        return 0;
    }

    hierholzer(s);
    if ((int)path.size() != m + 1) { // 边没走完，说明有边的点不连通
        cout << "NO\n";
        return 0;
    }
    reverse(path.begin(), path.end());
    for (int i = 0; i < (int)path.size(); i++) cout << path[i] << " \n"[i + 1 == (int)path.size()];
    return 0;
}
Python

C++ 版抽成 EulerPathUndirected 结构体（建图 / 判定 / 构造 / 入口分层），Python 版抽成自由函数。

python 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

        # 无向图欧拉路 / 欧拉回路（Hierholzer 迭代版）：返回顶点序列，无解返回 None，无边返回 []。
# 边以 (u, v) 列表传入，编号按下标 1..m；点编号 1..n；自环度数加 2，两条平行边构成回路。
# 判定：先连通（忽略孤立点），再要求奇度点个数为 0（回路）或 2（路径）。
# 全孤立点（m == 0）返回 []，对应 C++ 输出空行；全程迭代，无递归深度问题。

type RawEdge = tuple[int, int]  # 无向边 (u, v)


def euler_path_undirected(n: int, edges: list[RawEdge]) -> list[int] | None:
    """返回一条恰好用完所有边的顶点序列；不存在欧拉路时返回 None。"""
    m = len(edges)
    g: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]  # g[u] 存 (邻点, 边号)
    deg = [0] * (n + 1)

    for eid in range(1, m + 1):
        u, v = edges[eid - 1]
        g[u].append((v, eid))
        g[v].append((u, eid))
        if u == v:
            deg[u] += 2  # 自环给 u 贡献两条「半条边」，度数为偶数
        else:
            deg[u] += 1
            deg[v] += 1

    first = -1
    for i in range(1, n + 1):
        if deg[i] > 0:
            first = i
            break
    if first == -1:
        return []  # 一条边都没有：空序列

    vis = [False] * (n + 1)
    st = [first]
    vis[first] = True
    while st:
        u = st.pop()
        for v, _ in g[u]:
            if not vis[v]:
                vis[v] = True
                st.append(v)

    for i in range(1, n + 1):
        if deg[i] > 0 and not vis[i]:
            return None  # 有边的点不在同一连通块

    odd_count = 0
    start = first
    for i in range(1, n + 1):
        if deg[i] % 2 == 1:
            odd_count += 1
            start = i  # 有奇度点时以最后一个奇度点为起点（C++ 同此写法）

    if odd_count != 0 and odd_count != 2:
        return None  # 奇度点只能有 0 或 2 个

    used = [False] * (m + 1)
    it = [0] * (n + 1)
    stack_path = [start]
    path: list[int] = []
    while stack_path:
        u = stack_path[-1]
        while it[u] < len(g[u]) and used[g[u][it[u]][1]]:
            it[u] += 1
        if it[u] == len(g[u]):
            path.append(u)
            stack_path.pop()
        else:
            v, eid = g[u][it[u]]
            it[u] += 1
            used[eid] = True
            stack_path.append(v)

    if len(path) != m + 1:
        return None  # 兜底：没走完所有边
    path.reverse()
    return path

有向图模板

C++
cpp 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211

        #include <bits/stdc++.h>
using namespace std;

// 有向图欧拉路 / 欧拉回路（Hierholzer 算法）
// 输入：
//   n m
//   m 行 u v，表示 u -> v
// 输出：
//   一条欧拉路（或欧拉回路）的顶点序列，不存在时输出 NO
//
// 代码分层：
//   1. 建图层：init / add_edge
//   2. 判定层：connected（底图连通性）+ check_degree（出入度条件）
//   3. 构造层：hierholzer（算法本体，只管在有解时走出路径）
//   4. 入口层：solve（把判定和串起来）+ main（输入输出）
//
// 存在性条件（两个都要满足）：
//   1. 底图（忽略方向后）所有非孤立点连通；
//   2. 欧拉回路：每个点出度 == 入度；
//      欧拉路：恰好一个点出度 = 入度 + 1（起点），
//              恰好一个点入度 = 出度 + 1（终点），其余点出入度相等。
// 时间复杂度 O(n + m)。

struct EulerPathDirected {
    struct Edge {
        int to;
        int id; // 边的编号，用来标记这条边是否已经走过（重边靠编号区分）
    };

    int n = 0;
    int edge_cnt = 0; // 已加入的边数
    vector<vector<Edge>> g;
    vector<int> indeg, outdeg;

    void init(int _n) {
        n = _n;
        edge_cnt = 0;
        g.assign(n + 1, vector<Edge>());
        indeg.assign(n + 1, 0);
        outdeg.assign(n + 1, 0);
    }

    // 加一条有向边 u -> v
    void add_edge(int u, int v) {
        ++edge_cnt;
        g[u].push_back({v, edge_cnt});
        ++outdeg[u];
        ++indeg[v];
    }

    // ---- 判定层 ----

    // 条件 1：底图（忽略方向）中所有非孤立点是否连通。
    // 孤立点不参与判断：它们既不影响欧拉路的存在性，也不会出现在路径里。
    bool connected() {
        // 找任意一个「有边相连」的点作为 DFS 起点
        int first = -1;
        for (int i = 1; i <= n; ++i) {
            if (indeg[i] + outdeg[i] > 0) {
                first = i;
                break;
            }
        }
        // 边界：图中没有任何边，视为连通（此时欧拉路是空序列）
        if (first == -1) return true;

        // 底图邻接表，只用来判连通，不参与路径构造
        vector<vector<int>> weak(n + 1);
        for (int u = 1; u <= n; ++u) {
            for (const auto &e : g[u]) {
                weak[u].push_back(e.to);
                weak[e.to].push_back(u);
            }
        }

        // 迭代 DFS 检查连通性（递归写法在链状图上可能爆栈）
        vector<char> vis(n + 1, 0);
        stack<int> st;
        st.push(first);
        vis[first] = 1;
        while (!st.empty()) {
            int u = st.top();
            st.pop();
            for (int v : weak[u]) {
                if (!vis[v]) {
                    vis[v] = 1;
                    st.push(v);
                }
            }
        }

        for (int i = 1; i <= n; ++i) {
            if (indeg[i] + outdeg[i] > 0 && !vis[i]) return false;
        }
        return true;
    }

    // 条件 2：统计度数特殊的点，通过判定时 start 是合法起点。
    // 出度 = 入度 + 1 的点只可能是起点，入度 = 出度 + 1 的点只可能是终点，
    // 其余点必须出入度相等，否则无解。
    bool check_degree(int &start) {
        start = -1;
        for (int i = 1; i <= n; ++i) {
            if (indeg[i] + outdeg[i] > 0) {
                start = i; // 回路情形的默认起点
                break;
            }
        }

        int start_count = 0, end_count = 0;
        for (int i = 1; i <= n; ++i) {
            if (outdeg[i] == indeg[i] + 1) {
                ++start_count;
                start = i; // 唯一的起点候选
            } else if (indeg[i] == outdeg[i] + 1) {
                ++end_count;
            } else if (indeg[i] != outdeg[i]) {
                return false;
            }
        }

        // 合法情况只有两种：欧拉路（1 个起点 + 1 个终点）或欧拉回路（全部平衡）
        bool has_path = (start_count == 1 && end_count == 1);
        bool has_circuit = (start_count == 0 && end_count == 0);
        return has_path || has_circuit;
    }

    // ---- 构造层 ----

    // Hierholzer 算法本体：从 start 出发走出一条用完所有边的路径。
    // 前提：connected() 与 check_degree() 都已通过。
    // 返回顶点序列，正常时长度为边数 + 1。
    vector<int> hierholzer(int start) {
        vector<char> used(edge_cnt + 1, 0); // used[id]：第 id 条边是否已走
        // iter[u]：u 的「当前弧」，指向第一条还没走过的出边。
        // 走过的边不再扫描，保证每条边只被处理一次，总复杂度 O(n + m)。
        // 易错点：不要每次从 g[u][0] 重新扫，否则退化到 O(m^2)。
        vector<int> iter(n + 1, 0), stack_path, path;
        stack_path.push_back(start);

        while (!stack_path.empty()) {
            int u = stack_path.back();
            // 跳过已经走过的出边（重边可能出现连续多条已用边）
            while (iter[u] < (int)g[u].size() && used[g[u][iter[u]].id]) {
                ++iter[u];
            }

            if (iter[u] == (int)g[u].size()) {
                // u 的出边走完了：u 是当前这条「死胡同」的端点，
                // 此时才把 u 记入 path（后序收集，最终 reverse 后才是正序）。
                path.push_back(u);
                stack_path.pop_back();
            } else {
                Edge e = g[u][iter[u]++]; // 取走这条出边
                used[e.id] = 1;
                stack_path.push_back(e.to);
            }
        }

        // path 是「回溯顺序」收集的，reverse 后才是从起点到终点的欧拉路。
        reverse(path.begin(), path.end());
        return path;
    }

    // ---- 入口层 ----

    // 总入口：存在欧拉路/回路时把顶点序列写进 path 并返回 true。
    // 图中没有边时 path 是空序列，也视为有解。
    bool solve(vector<int> &path) {
        path.clear();
        int start = -1;
        if (!connected() || !check_degree(start)) return false;
        if (edge_cnt == 0) return true; // 边界：没有任何边，欧拉路是空序列

        path = hierholzer(start);
        // 理论上前面的判定已经保证有解，这里再兜底一次防御非法输入。
        if ((int)path.size() != edge_cnt + 1) {
            path.clear();
            return false;
        }
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    EulerPathDirected solver;
    solver.init(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        solver.add_edge(u, v);
    }

    vector<int> path;
    if (!solver.solve(path)) {
        cout << "NO\n";
        return 0;
    }
    for (int i = 0; i < (int)path.size(); ++i) {
        if (i) cout << ' ';
        cout << path[i];
    }
    cout << '\n';
    return 0;
}
C++ 竞赛版

不用 struct 的精简写法：省去显式弱连通检查，靠 path 长度兜底判定，适合比赛现场手写。

cpp 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

        #include <bits/stdc++.h>
using namespace std;

// 有向图欧拉路 / 欧拉回路竞赛精简版（Hierholzer，不用 struct）
// 输入 n m 与 m 条有向边 u v（u -> v），输出顶点序列，无解输出 NO
// 判定：恰一个起点出度 = 入度 + 1，恰一个终点入度 = 出度 + 1，其余出入度相等（回路则全部相等）
// 弱连通不用单独判：走不完所有边（path 长度 != m+1）就是不弱连通
// 口诀：走不动了再记点，记完 reverse

int n, m;
vector<vector<pair<int, int>>> g; // 邻接表 {终点, 边编号}
vector<int> in, out, used, cur, path;

void hierholzer(int s) {
    vector<int> st = {s};
    while (!st.empty()) {
        int u = st.back();
        // 跳过已走的边；cur 保证每条边只被扫过常数次，总复杂度 O(n+m)
        while (cur[u] < (int)g[u].size() && used[g[u][cur[u]].second]) cur[u]++;
        if (cur[u] == (int)g[u].size()) {
            path.push_back(u); // 走不动才记点（后序），reverse 后才是答案
            st.pop_back();
        } else {
            auto e = g[u][cur[u]++]; // 用掉这条出边，走向下一点
            used[e.second] = 1;
            st.push_back(e.first);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    g.assign(n + 1, {});
    in.assign(n + 1, 0);
    out.assign(n + 1, 0);
    used.assign(m + 1, 0);
    cur.assign(n + 1, 0);
    for (int id = 1; id <= m; id++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back({v, id});
        out[u]++;
        in[v]++;
    }

    int s = -1, sc = 0, tc = 0;
    for (int i = 1; i <= n; i++) {
        if (out[i] == in[i] + 1) sc++, s = i; // 起点候选
        else if (in[i] == out[i] + 1) tc++;   // 终点候选
        else if (in[i] != out[i]) {
            cout << "NO\n";
            return 0;
        }
    }
    // 易错点：必须恰 0 个或恰 1 对起终点；多对时 path 长度能骗过检查但输出非法
    if (sc > 1 || tc > 1) {
        cout << "NO\n";
        return 0;
    }
    if (s == -1) { // 全平衡是回路，任取一个有出边的点出发
        for (int i = 1; i <= n; i++)
            if (out[i]) { s = i; break; }
    }
    if (s == -1) { // 边界：没有任何边，欧拉路是空序列
        cout << '\n';
        return 0;
    }

    hierholzer(s);
    if ((int)path.size() != m + 1) { // 边没走完，说明底图不弱连通
        cout << "NO\n";
        return 0;
    }
    reverse(path.begin(), path.end());
    for (int i = 0; i < (int)path.size(); i++) cout << path[i] << " \n"[i + 1 == (int)path.size()];
    return 0;
}
Python

C++ 版抽成 EulerPathDirected 结构体（建图 / 判定 / 构造 / 入口分层），Python 版抽成自由函数。

python 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

        # 有向图欧拉路 / 欧拉回路（Hierholzer 迭代版）：返回顶点序列，无解返回 None，无边返回 []。
# 边以 (u, v) 列表传入，编号按下标 1..m；点编号 1..n。
# 判定：先弱连通（忽略孤立点），再要求所有点 in == out（回路），或恰有一个 out == in + 1 的起点
# 与一个 in == out + 1 的终点（路径）。全孤立点（m == 0）返回 []，对应 C++ 输出空行。
# 全程迭代，无递归深度问题。

type RawEdge = tuple[int, int]  # 有向边 (u, v)


def euler_path_directed(n: int, edges: list[RawEdge]) -> list[int] | None:
    """返回一条恰好用完所有边的顶点序列；不存在欧拉路时返回 None。"""
    m = len(edges)
    g: list[list[tuple[int, int]]] = [[] for _ in range(n + 1)]  # g[u] 存 (终点, 边号)
    weak: list[list[int]] = [[] for _ in range(n + 1)]  # 只看连通性用的无向邻接表
    indeg = [0] * (n + 1)
    outdeg = [0] * (n + 1)

    for eid in range(1, m + 1):
        u, v = edges[eid - 1]
        g[u].append((v, eid))
        weak[u].append(v)
        weak[v].append(u)
        outdeg[u] += 1
        indeg[v] += 1

    # 第一个有边的点，用来做连通性检查，也是回路时的默认起点。
    first = -1
    for i in range(1, n + 1):
        if indeg[i] + outdeg[i] > 0:
            first = i
            break
    if first == -1:
        return []  # 一条边都没有：空序列

    vis = [False] * (n + 1)
    st = [first]
    vis[first] = True
    while st:
        u = st.pop()
        for v in weak[u]:
            if not vis[v]:
                vis[v] = True
                st.append(v)

    for i in range(1, n + 1):
        if indeg[i] + outdeg[i] > 0 and not vis[i]:
            return None  # 有边的点不在同一弱连通块

    start_count = 0
    end_count = 0
    start = first
    for i in range(1, n + 1):
        if outdeg[i] == indeg[i] + 1:
            start_count += 1
            start = i
        elif indeg[i] == outdeg[i] + 1:
            end_count += 1
        elif indeg[i] != outdeg[i]:
            return None  # 度数差超过 1，不可能有欧拉路

    has_path = start_count == 1 and end_count == 1
    has_circuit = start_count == 0 and end_count == 0
    if not has_path and not has_circuit:
        return None

    used = [False] * (m + 1)
    it = [0] * (n + 1)  # 每个点下一条待尝试的出边下标
    stack_path = [start]
    path: list[int] = []
    while stack_path:
        u = stack_path[-1]
        while it[u] < len(g[u]) and used[g[u][it[u]][1]]:
            it[u] += 1
        if it[u] == len(g[u]):
            path.append(u)  # 没有未用出边了，回退时把它接到答案末尾
            stack_path.pop()
        else:
            v, eid = g[u][it[u]]
            it[u] += 1
            used[eid] = True
            stack_path.append(v)

    if len(path) != m + 1:
        return None  # 没走完所有边（理论上前面判定保证不会发生，这里兜底）
    path.reverse()  # 出栈顺序是逆序，反转后才是欧拉路
    return path

测试用例

无向图欧拉路：

输入:
5 6
1 2
2 3
3 4
4 2
3 5
5 1

一种合法输出:
2 1 5 3 4 2 3

解释：输出不唯一，只要相邻顶点之间对应输入中的一条未使用边，并且 66 条边都恰好用一次即可。

对照下图走一遍 Hierholzer，边上的编号是走边顺序：从起点 22 沿 ①②③ 走到 33，再钻进小环 ④⑤⑥ 绕回 33。此时所有边都已用完，回溯收集顺序是 3,2,4,3,5,1,23, 2, 4, 3, 5, 1, 2，反转后正是 2,1,5,3,4,2,32, 1, 5, 3, 4, 2, 3。

无向图测试用例的欧拉路走法：按编号 1 到 6 的箭头从起点 2 走到终点 3，六条边各用一次，其中 4 5 6 构成先走完的小环

有向图欧拉回路：

输入:
5 6
1 2
2 3
3 1
3 4
4 5
5 3

一种合法输出:
1 2 3 4 5 3 1

对照下图：从 11 沿 ①② 走到 33，钻进小环 ③④⑤ 绕回 33，再沿 ⑥ 回到 11。回溯收集顺序是 1,3,5,4,3,2,11, 3, 5, 4, 3, 2, 1，反转后正是 1,2,3,4,5,3,11, 2, 3, 4, 5, 3, 1。

有向图测试用例的欧拉回路走法：按编号 1 到 6 的箭头从顶点 1 出发绕两个三角形回到顶点 1，其中 3 4 5 构成先走完的小环

不可行用例：

输入:
4 2
1 2
3 4

输出:
NO

解释：忽略孤立点后，有边顶点不在同一个连通块中。

应用分类详解

欧拉路的本质是：每条边恰好使用一次的路径构造问题。

一、一笔画与边覆盖

  • 典型模式： 题目要求每条边、每条路、每张牌或每个连接关系恰好使用一次。
  • 识别信号： 出现“一笔画”“每条边恰好一次”“输出经过边的顺序”。
  • 核心建模： 把对象之间的连接关系建成边，用度数判定和 Hierholzer 构造路径。
应用场景 经典题目 核心思路
无向一笔画 luogu-P1341 字符当顶点，相邻字符关系当边
字典序路径 luogu-P2731 邻接表排序后做 Hierholzer
有向欧拉回路 luogu-P6066 按出边方向构造完整边序列

二、字符串拼接与 De Bruijn 图

  • 典型模式： 给出很多长度相同或相邻重叠的片段，要求拼成一个序列。
  • 识别信号： 片段之间通过前缀、后缀相接，每个片段必须使用一次。
  • 核心建模： 把长度 k−1k-1 的前缀和后缀当顶点，把一个长度 kk 的片段当有向边。
应用场景 经典题目 核心思路
单词接龙 luogu-P1127 单词首尾字符建边，找字典序欧拉路
DNA 片段拼接 De Bruijn 图模型 k-mer 作为边，前后缀作为顶点
邮票/门牌序列 常见构造题 每个片段必须恰好使用一次

三、边必须重复覆盖的扩展

  • 典型模式： 要求每条边至少经过一次，并且总代价最小。
  • 识别信号： 出现“巡检所有道路”“邮递员路线”“允许重复走边”。
  • 核心建模： 如果图本来不是欧拉图，就需要补边或复制路径，让奇度点配对后变成欧拉回路。
应用场景 经典题目 核心思路
中国邮递员问题 邮差巡路模型 奇度点之间做最小代价配对
边覆盖巡检 luogu-P6628 把必须重复的部分转成欧拉化后的走法
路网巡回 工程巡检模型 先补足度数条件，再输出欧拉回路

经典例题

  1. luogu-P1341 无序字母对 每个字母是顶点，每个字母对是无向边。题目要求输出一条使用所有字母对的序列，本质就是无向欧拉路。

  2. luogu-P2731 Riding the Fences 模板型无向欧拉路题。额外要求字典序尽量小，需要对邻接表排序，并从合适的最小起点开始。

  3. luogu-P1127 词链 单词看成从首字母到尾字母的一条有向边。每个单词必须用一次，因此需要判断有向欧拉路，并处理字典序。

  4. luogu-P6066 Watchcow 有向欧拉回路模型。重点是理解每条有向边只能按方向使用一次。

  5. luogu-P6628 丁香之路 欧拉路的扩展题。不是简单套模板，而是要先把重复经过边的需求转成欧拉化后的图。

字典序最小路径

如果题目要求字典序最小，常见处理方式是：

  1. 邻接表按终点编号排序。
  2. 若用递归或栈后序生成答案，要注意答案会反转。
  3. 根据实现选择升序取边后反转答案，或降序存边用 pop_back() 取最小边。
  4. 起点也要按判定条件选择最小可行点：有两个奇度点时取较小的奇度点；欧拉回路时取最小的有边点。

字典序问题的细节和“答案是后序产生的”强相关。调试时不要只看取边顺序，还要看最后是否做了 reverse。