「一本通 3.7 例 1」欧拉回路

形式化题目

给定一个可能包含重边和自环的图 $G = (V, E)$ ，其中 $|V| = n$ ， $|E| = m$ 。包含两个子任务：

$t = 1$ ： $G$ 为无向图。
$t = 2$ ： $G$ 为有向图。

判断图中是否存在欧拉回路（即一条经过图中每条边恰好一次且回到起点的闭路径）：

若不存在，输出 NO。
若存在，输出 YES，并输出回路中依次经过的边编号序列 $p_1, p_2, \dots, p_m$ 。对于无向图，若逆着输入方向走第 $e$ 条边，输出 $-e$ ；对于有向图，输出边的原始编号。

正解

思路

欧拉回路的存在性判定包含两个条件：

度数条件：
- 无向图：每个顶点的度数必须为偶数（ $\text{deg}(v) \equiv 0 \pmod 2$ ）。
- 有向图：每个顶点的入度必须等于出度（ $\text{in\_deg}(v) = \text{out\_deg}(v)$ ）。
连通性条件：所有度数大于 $0$ 的边必须属于同一个连通分量。

若度数条件满足，我们采用 Hierholzer 算法 构造欧拉回路。

朴素做法及其性能瓶颈

若直接使用深度优先搜索（DFS）遍历出边，在存在大量重边或星状密集边的图上，每次访问某顶点都从其邻接表头从头扫描已走过的边，会导致大量无效的跳过检查，时间复杂度退化至 $O(m^2)$ 。同时，当回路长度达到 $2 \times 10^5$ 时，过深的递归会引发栈溢出。

当前弧优化与显式栈

当前弧优化（Current Arc Optimization）：为每个节点维护一个指针 cur[u]，记录当前节点尚未尝试访问的下一条出边。每次遍历过一条边后，直接将 cur[u] 移至下一条出边 nxt[e]。由于每条边只会被“尝试走”常数次，邻接表遍历的总开销被严格限制在 $O(n + m)$ 。
非递归显式栈：使用顶点栈 stk_u 与边栈 stk_e 模拟递归回溯过程。
- 当栈顶顶点还有未访问边时，沿该边前进，并将新顶点与边压入栈；
- 当栈顶顶点的所有出边均已探索完毕时，弹出栈顶顶点，同时将进入该顶点的边记录至答案序列（后序记录）；
- 最终将边序列翻转，即得到正序的欧拉回路。
连通性校验：最终遍历得到的回路边数若小于 $m$ ，说明存在未被访问到的孤立子环（即图中包含多个有边的连通块），判定为无解并输出 NO。

代码

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
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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 16:25
# update_at: 2026-09-30 16:25

import sys

# 边访问标记
VISITED_FLAG = 1


def euler_undirected(n: int, m: int, head: list[int], to: list[int], nxt: list[int], eid: list[int]) -> list[int]:
    """Hierholzer 非递归求无向图欧拉回路：当前弧优化推进，退栈时记录逆序回路。"""
    used = [0] * (m + 1)
    cur = head[:]
    tour: list[int] = []
    stk_u: list[int] = [next((v for v in range(1, n + 1) if head[v] != -1), 1)]
    stk_e: list[int] = []

    while stk_u:
        u = stk_u[-1]
        e = cur[u]
        while e != -1 and used[abs(eid[e])]:
            e = nxt[e]
        cur[u] = e
        if e != -1:
            edge_id = eid[e]
            used[abs(edge_id)] = VISITED_FLAG
            cur[u] = nxt[e]
            stk_u.append(to[e])
            stk_e.append(edge_id)
        else:
            stk_u.pop()
            if stk_e:
                tour.append(stk_e.pop())

    tour.reverse()
    return tour


def euler_directed(n: int, m: int, head: list[int], to: list[int], nxt: list[int], eid: list[int]) -> list[int]:
    """Hierholzer 非递归求有向图欧拉回路：当前弧优化推进，退栈时记录逆序回路。"""
    used = [0] * (m + 1)
    cur = head[:]
    tour: list[int] = []
    stk_u: list[int] = [next((v for v in range(1, n + 1) if head[v] != -1), 1)]
    stk_e: list[int] = []

    while stk_u:
        u = stk_u[-1]
        e = cur[u]
        while e != -1 and used[eid[e]]:
            e = nxt[e]
        cur[u] = e
        if e != -1:
            edge_id = eid[e]
            used[edge_id] = VISITED_FLAG
            cur[u] = nxt[e]
            stk_u.append(to[e])
            stk_e.append(edge_id)
        else:
            stk_u.pop()
            if stk_e:
                tour.append(stk_e.pop())

    tour.reverse()
    return tour


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    try:
        t = int(next(data))
    except StopIteration:
        return
    n, m = int(next(data)), int(next(data))

    if m == 0:
        print("YES\n")
        return

    deg = [0] * (n + 1)
    head = [-1] * (n + 1)

    if t == 1:
        # 无向图前向星：边成对存储，第 i 条边编号为 +(i+1) 与 -(i+1)
        tot = m * 2
        to = [0] * tot
        nxt = [0] * tot
        eid = [0] * tot
        edge_cnt = 0
        for i in range(1, m + 1):
            u, v = int(next(data)), int(next(data))
            deg[u] += 1
            deg[v] += 1
            to[edge_cnt], nxt[edge_cnt], eid[edge_cnt] = v, head[u], i
            head[u] = edge_cnt
            edge_cnt += 1
            to[edge_cnt], nxt[edge_cnt], eid[edge_cnt] = u, head[v], -i
            head[v] = edge_cnt
            edge_cnt += 1

        degree_valid = all(d % 2 == 0 for d in deg)
        if not degree_valid:
            print("NO")
            return

        tour = euler_undirected(n, m, head, to, nxt, eid)
    else:
        # 有向图前向星：记录出度与入度之差
        to = [0] * m
        nxt = [0] * m
        eid = [0] * m
        edge_cnt = 0
        for i in range(1, m + 1):
            u, v = int(next(data)), int(next(data))
            deg[u] -= 1
            deg[v] += 1
            to[edge_cnt], nxt[edge_cnt], eid[edge_cnt] = v, head[u], i
            head[u] = edge_cnt
            edge_cnt += 1

        degree_valid = all(d == 0 for d in deg)
        if not degree_valid:
            print("NO")
            return

        tour = euler_directed(n, m, head, to, nxt, eid)

    connected = len(tour) == m
    if not connected:
        print("NO")
        return

    print("YES")
    print(" ".join(map(str, tour)))


if __name__ == "__main__":
    solve()

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 06:19
 * update_at: 2026-10-05 06:19
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100005; // 点数上限
const int MAXM = 200005; // 边数上限

int t, n, m;
int head[MAXN];   // 链式前向星头指针，head[u] 为 0 表示没有出边
int nxt[MAXM * 2];
int to_[MAXM * 2];
int eid[MAXM * 2]; // eid[i] 为第 i 条弧对应的边的带符号编号：无向图反向弧为负，有向图为正
bool used[MAXM];   // used[i] 表示第 i 条边是否已被走过
int cur[MAXN];     // cur[u] 当前弧优化：记录 u 下一条要尝试的弧下标

int ans[MAXM];  // 逆序记录的回路边编号
int ans_cnt = 0;

// 加一条 u -> v、边号为 e 的弧
void add_edge(int u, int v, int e) {
    static int cnt = 0;
    cnt++;
    to_[cnt] = v;
    nxt[cnt] = head[u];
    eid[cnt] = e;
    head[u] = cnt;
}

// 非递归 Hierholzer：当前弧推进，退栈时后序记录进入的边，得到逆序回路
void hierholzer(int start) {
    static int stk_u[MAXN * 2]; // 栈里存点
    static int stk_e[MAXM];     // 栈里存进入该点用的边
    int top_u = 0, top_e = 0;

    for (int i = 1; i <= n; i++) cur[i] = head[i];
    stk_u[++top_u] = start;

    while (top_u > 0) {
        int u = stk_u[top_u];
        int e = cur[u];
        if (e != 0) {
            // 该弧对应的边还没走过才走：无向图时双向各占一条弧，用 used[|eid|] 去重
            int id = eid[e];
            int pos = id < 0 ? -id : id;
            cur[u] = nxt[e];
            if (used[pos]) continue;
            used[pos] = true;
            stk_u[++top_u] = to_[e];
            stk_e[++top_e] = id;
        } else {
            top_u--;
            if (top_e > 0) {
                ans_cnt++;
                ans[ans_cnt] = stk_e[top_e];
                top_e--;
            }
        }
    }
}

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

    cin >> t >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        if (t == 1) {
            add_edge(u, v, i);
            add_edge(v, u, -i); // 无向图：反向弧记为负号
        } else {
            add_edge(u, v, i);
        }
    }

    // m == 0 时：没有边，显然可以"一笔画"，输出空方案
    if (m == 0) {
        cout << "YES" << '\n' << '\n';
        return 0;
    }

    // 度数条件：无向图所有点度数为偶数，有向图每点入度等于出度
    bool ok = true;
    if (t == 1) {
        static int deg[MAXN]; // deg[v] 为 v 的度数
        for (int i = 1; i <= n; i++) deg[i] = 0;
        for (int u = 1; u <= n; u++) {
            for (int e = head[u]; e != 0; e = nxt[e]) {
                if (eid[e] > 0) { // 只数正向弧，每条无向边恰好一条，避免双向重复计数
                    deg[u]++;
                    deg[to_[e]]++;
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            if (deg[i] % 2 != 0) ok = false;
        }
    } else {
        static int outd[MAXN], ind[MAXN]; // 出度与入度
        for (int i = 1; i <= n; i++) outd[i] = ind[i] = 0;
        for (int u = 1; u <= n; u++) {
            for (int e = head[u]; e != 0; e = nxt[e]) {
                outd[u]++;
                ind[to_[e]]++;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (ind[i] != outd[i]) ok = false;
        }
    }
    if (!ok) {
        cout << "NO" << '\n';
        return 0;
    }

    // 从任意一个有边的点出发
    int start = 1;
    for (int i = 1; i <= n; i++) {
        if (head[i] != 0) {
            start = i;
            break;
        }
    }
    hierholzer(start);

    // 走过的边数不足 m：图里有边的部分不连通
    if (ans_cnt != m) {
        cout << "NO" << '\n';
        return 0;
    }

    cout << "YES" << '\n';
    // ans 里是逆序回路，倒序输出即为正序
    for (int i = m; i >= 1; i--) {
        cout << ans[i] << (i == 1 ? '\n' : ' ');
    }
    return 0;
}

复杂度

时间复杂度： $\mathcal{O}(n + m)$ 。读取输入、度数校验需要 $\mathcal{O}(n + m)$ ；由于当前弧优化的存在，每条边仅被压栈与退栈常数次，Hierholzer 算法耗时 $\mathcal{O}(n + m)$ ；输出边序列耗时 $\mathcal{O}(m)$ 。
空间复杂度： $\mathcal{O}(n + m)$ 。前向星存图、当前弧数组、栈以及结果边列表的空间开销均与 $n, m$ 成线性关系。

图示解析

以样例 1（无向图三角形回路）为例，展示 Hierholzer 算法通过退栈后序记录、再反转得到欧拉回路的过程：

graph LR
    1((1)) ---|边 1| 2((2))
    2 ---|边 2| 3((3))
    1 ---|边 3| 3

从顶点 $1$ 出发，依次走边 $1 \to 2$ 、边 $2 \to 3$ 、反向边 $-3 \to 1$ 。
此时顶点 $1$ 的出边均已访问完毕，开始回溯退栈：
- 退栈 $1$ ，记录进入边 $-3$ ；
- 退栈 $3$ ，记录进入边 $2$ ；
- 退栈 $2$ ，记录进入边 $1$ ；
退栈收集的边序列为 [-3, 2, 1]，将其翻转即得合法回路 [1, 2, -3]。

总结

欧拉回路问题的关键在于：

快速判定度数偶性与出入度平衡；
Hierholzer 算法中的当前弧优化，防止在稠密重边下邻接表反复回溯退化；
使用显式栈避免深层图结构下的调用栈溢出。

「一本通 3.7 例 1」欧拉回路

目录

形式化题目

正解

思路

朴素做法及其性能瓶颈

当前弧优化与显式栈

代码

复杂度

图示解析

总结