骑马修栅栏

形式化题目

给定一个无向连通图 $G$ （ $F \leqslant 1024$ 条边，顶点编号 $1 \sim 500$ ，可能有重边、无自环以外的限制），求一条欧拉路径——每条边恰好经过一次——并把它表示为依次经过的 $F+1$ 个顶点。多解时输出序列字典序最小的一条。数据保证有解。

正解

思路

「每条边恰好走一次」正是欧拉路径的定义。连通图存在欧拉路径当且仅当奇度顶点个数为 $0$ （欧拉回路）或 $2$ （路径，两个奇度点分别是两端）。题目保证有解，所以不需要判无解，只需要构造出字典序最小的那条。

第一步：选起点。 若有两个奇度点，欧拉路径必须以它们为两端，起点只能取较小的那个；若没有奇度点，任何点出发都存在欧拉回路，取最小顶点即可。

第二步：贪心 + Hierholzer。 每到一个顶点，贪心地走当前编号最小的可用邻点。担心贪心走进"死胡同"（把某个点剩余的边切断）？关键在于：如果贪心选小邻点后走进了死胡同，那个死胡同点的剩余度数此刻必为奇——它注定是整条欧拉路径的终点。Hierholzer 算法恰好利用这一点：沿贪心方向一路入栈，走不动时出栈记录，出栈点若是"提前走完"的点，它的剩余边会在回溯拼接时被后面的环补上，最终结果仍是合法欧拉路径。因此"每步取当前最小可行邻点"得到的就是字典序最小的欧拉路径。

具体流程（迭代版 Hierholzer）：

每个点的邻接表按另一端点升序排序；
栈顶为 $v$ ：跳过已经走过的边（used[id] 标记 + cur 当前弧，保证每条边只被扫过常数次），取剩下的最小邻点 $u$ ，把这条栅栏标记为已走， $u$ 入栈；
若 $v$ 没有剩余邻点， $v$ 出栈加入 path（走不动才记点）；
path 反转即为答案。

先看样例的图结构（1 出发，两个奇度点是 1 和 7，起点取 1）：

graph LR
    1 --- 2
    2 --- 3
    3 --- 4
    4 --- 2
    4 --- 5
    2 --- 5
    5 --- 6
    5 --- 7
    4 --- 6

图中每条边恰好被走一次，答案 1 2 3 4 2 5 4 6 5 7。注意走到 6 时 6 的边已走完，先出栈；随后 5、4…依次回溯出栈，反转后得到完整路径。

步骤	栈顶动作	说明
1→2→3→4	一路取最小邻点入栈	贪心向深处走
顶点 2（第二次）	无剩余邻点，出栈	路径的"中段"先定下来
5、4、6	6 走完出栈，5、4 继续走剩余边	回溯中拼接子回路
7	走完出栈	终点（另一个奇度点）最后出栈

path 逆序弹出，反转即字典序最小的答案。

代码

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#!/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 07:43
# update_at: 2026-09-30 07:43

import sys


def hierholzer(adj: dict[int, list[int]]) -> list[int]:
    """非递归 Hierholzer：求字典序最小的欧拉路径顶点序列。"""
    odd = [v for v in adj if len(adj[v]) % 2]        # 度为奇数的顶点
    # 有奇点时从最小的奇点出发（保证存在欧拉路径），否则全为偶点任取最小点
    start = min(odd) if odd else min(adj)
    for nbrs in adj.values():
        nbrs.sort()                                  # 每次贪心走最小的邻点 → 字典序最小
    stack, path = [start], []
    while stack:
        v = stack[-1]
        if adj[v]:                                   # 还有未走的边，继续往深处走
            u = adj[v].pop(0)                      # 取最小邻点；无向边两个方向同时删掉
            adj[u].remove(v)
            stack.append(u)
        else:
            u = stack.pop()
            path.append(u)
    return path[::-1]                                # 逆序弹出，反转得到路径


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    fences = next(data)                              # 栅栏数 F，即边数
    adj: dict[int, list[int]] = {}
    for _ in range(fences):
        u, v = next(data), next(data)
        adj.setdefault(u, []).append(v)
        adj.setdefault(v, []).append(u)

    print('\n'.join(map(str, hierholzer(adj))))


if __name__ == "__main__":
    solve()

C++ 版（同一算法，精简版迭代 Hierholzer：used 标记已走边 + cur 当前弧）：

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/**
 * 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 00:04
 * update_at: 2026-10-13 16:35
 */
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long ll;

// 骑马修栅栏：每条栅栏恰好走一次 = 无向图欧拉路
// 精简版迭代 Hierholzer（不用 struct 图、不用递归）：
// 口诀「走不动了再记点，记完 reverse」
// 字典序最小：邻接表按另一端点升序，每步贪心走当前最小的可用邻点

const int MAXV = 500;  // 顶点编号 1~500
const int MAXF = 1024; // 栅栏数 F <= 1024，路径长度为 F+1

struct Edge {
    int to; // 这条栅栏的另一个端点
    int id; // 栅栏编号，用来标记这条边走过没有
};

vector<Edge> g[MAXV + 5]; // g[v]：v 连出的所有栅栏，按 to 升序
int deg[MAXV + 5];        // deg[v]：v 的度数，自环一条边要 +2
int used[MAXF + 5];       // used[id]：第 id 条栅栏是否已经走过
int cur[MAXV + 5];        // cur[v]：当前弧，v 的边从这里继续找，每条边只被扫过常数次
int path[MAXF + 5];       // path[]：走不动时记下的顶点，反转后才是答案
int path_len;             // path_len：路径上的顶点个数

// 邻接表排序用：按另一端点编号升序，保证每步都能贪心取最小邻点
bool cmp_edge(const Edge &a, const Edge &b) {
    return a.to < b.to;
}

// 从起点 s 出发走欧拉路：显式栈模拟递归，避免 F 条边递归爆栈
void hierholzer(int s) {
    int stack_vertex[MAXF + 5]; // 当前还没走完的顶点栈
    int top = 0;
    stack_vertex[++top] = s;
    while (top > 0) {
        int u = stack_vertex[top];
        ll sz = g[u].size(); // 当前点还没走的边数上界
        // 跳过已经走过的边；cur 保证总复杂度 O(F)
        while (cur[u] < sz && used[g[u][cur[u]].id] == 1) cur[u]++;
        if (cur[u] == sz) {
            path[++path_len] = u; // 走不动才记点（后序），最后要 reverse
            top--;
        } else {
            Edge e = g[u][cur[u]]; // 用掉这条边，走向另一端点
            cur[u]++;
            used[e.id] = 1;
            stack_vertex[++top] = e.to;
        }
    }
}

int main() {
    int fences;
    scanf("%d", &fences);

    for (int id = 1; id <= fences; id++) {
        int u, v;
        scanf("%d %d", &u, &v);
        g[u].push_back(Edge{v, id});
        g[v].push_back(Edge{u, id}); // 无向边两个方向共用编号，不会来回走同一条
        deg[u] += (u == v ? 2 : 1);  // 易错点：自环让度数 +2
        if (u != v) deg[v]++;
    }

    // 每个点的邻接表升序排序：每步贪心走最小邻点，答案才是字典序最小
    for (int v = 1; v <= MAXV; v++) sort(g[v].begin(), g[v].end(), cmp_edge);

    // 奇度点只能是欧拉路的两端，起点取较小的那个；
    // 全偶度时是欧拉回路，任取编号最小的有边点（题目保证有解，F >= 1 一定找得到）
    int start = -1;
    for (int v = 1; v <= MAXV; v++) {
        if (deg[v] % 2 == 1) {
            start = v;
            break;
        }
    }
    if (start == -1) {
        for (int v = 1; v <= MAXV; v++) {
            if (deg[v] > 0) {
                start = v;
                break;
            }
        }
    }

    hierholzer(start);

    // path 是后序记录，倒着输出就是从起点到终点的顺序，每行一个顶点
    for (int i = path_len; i >= 1; i--) printf("%d\n", path[i]);
    return 0;
}

复杂度

建图与排序： $O(F \log F)$ 。
Hierholzer 每条边进出栈各一次。Python 用 list.pop(0) / remove 删边，单次 $O(F)$ ，总计 $O(F^2) \approx 10^6$ （ $F \leqslant 1024$ ），瞬间完成；C++ 用 used[id] 标记 + cur 当前弧删边，每条边只被扫过常数次，Hierholzer 部分 $O(F)$ 。
空间 $O(F)$ 。

总结

本题是欧拉路径的模板变体，考点有两个：一是把"每条栅栏恰好经过一次"识别为欧拉路径，用奇度点个数确定起点；二是"字典序最小"这一附加条件——把邻接表排序后每步贪心取最小邻点，配合 Hierholzer 的回栈拼接即可，不需要任何额外的搜索或 DP。

图示解析

样例欧拉路径走法

上面的 Mermaid 图展示原图无向结构；下表给出最终答案与每条边的对应关系，验证每条边恰好出现一次：

边	在路径中的位置
(1,2)	第 1 步
(2,3)	第 2 步
(3,4)	第 3 步
(4,2)	第 4 步（回到 2）
(2,5)	第 5 步
(5,4)	第 6 步
(4,6)	第 7 步
(6,5)	第 8 步
(5,7)	第 9 步（终点 7）

观察重点：路径两端 1 和 7 正是全图仅有的两个奇度点；中间点 2、4、5 各有偶数度，进多少次就出多少次。

目录

形式化题目

正解

思路

代码

复杂度

总结

图示解析

样例欧拉路径走法