【例题】一笔画问题

题目描述

一笔画的路径叫欧拉路，最后回到起点的叫欧拉回路。给定 $n$ 个点 $m$ 条边的无向图，输出任意一条欧拉路或欧拉回路。输入：第一行 $n, m$ ，接下来 $m$ 行每行一条边的两端。输出：一条合法路径。样例：输入 5 5 与边 $(1,2)(2,3)(3,4)(4,5)(5,1)$ ，输出 1 5 4 3 2 1。

思路

奇度点个数为 $0$ 或 $2$ 才有一笔画（本题保证有解），有奇点就从奇点出发。用 Hierholzer 算法：能走就走并压栈，栈顶无路可走时弹进出栈序列；每条边按「边编号」标记走过（按点对删边会误吞平行边），出栈序列逆序输出即为答案。

参考代码

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

import sys
from collections import defaultdict


def euler_path(adj: dict[int, list[tuple[int, int]]], deg: list[int], m: int) -> list[int]:
    """Hierholzer 迭代版：一路贪心走到底，走不动才把点记进路径；出栈顺序即答案。

    每条无向边各占一个编号（两端都能注销它），故 1-2 之间的平行边不会被漏掉。
    邻居按号码倒排后从栈顶取，每次便拿到最小邻居，输出与参考解一致。
    """
    used = [False] * m                              # used[e]：第 e 条边已被走掉
    odd = [v for v in range(1, len(deg)) if deg[v] % 2]
    start = max(odd) if odd else 1                  # 有奇点就从最大奇点出发，否则任取一点
    path: list[int] = []
    stack = [start]
    while stack:
        v = stack[-1]
        while adj[v] and used[adj[v][-1][1]]:       # 栈顶是已走过的边就弹掉
            adj[v].pop()
        if adj[v]:
            w, e = adj[v].pop()                     # 贪心走向还没用过的邻居
            used[e] = True
            stack.append(w)
        else:
            path.append(stack.pop())                # 无路可走，这个点正式落进路径
    return path                                     # 回溯顺序自后向前拼接，无需再反转


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    adj: dict[int, list[tuple[int, int]]] = defaultdict(list)
    deg = [0] * (n + 1)
    for e in range(m):
        a, b = next(data), next(data)
        adj[a].append((b, e))                       # 存 (邻居, 边编号)
        adj[b].append((a, e))
        deg[a] += 1
        deg[b] += 1
    for v in adj:
        adj[v].sort(key=lambda item: -item[0])      # 倒排，使栈顶 pop 出的是最小邻居

    print(' '.join(map(str, euler_path(adj, deg, m))))


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/**
 * 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 10:46
 * update_at: 2026-10-05 11:05
 */
#include <cstdio>

typedef long long ll;

const int MAXN = 1005;   // 点数上限
const int MAXM = 2005;   // 边数上限

// 无向图：每条边存两个方向的半边，用边编号标记是否走过（正确处理平行边）
struct Edge {
    ll to;   // 这条半边指向的点
    ll id;   // 所属无向边的编号
};

Edge edge[MAXM * 2];     // 邻接表：每条无向边存两条半边
ll head[MAXN];           // head[u]：u 的邻接表链头（-1 表示空）
ll nxt[MAXM * 2];        // 链表 next 指针
ll cnt_edge = 0;         // 半边计数器

bool used[MAXM];         // used[e]：第 e 条无向边是否已经走过
ll sta[MAXM + 10];       // 手写栈：沿途的点
ll top = 0;              // 栈顶指针
ll ans[MAXM + 10];       // 出栈序列（逆序输出后就是欧拉路）
ll len_ans = 0;          // 出栈序列长度
ll deg[MAXN];            // 每个点的度数，用来找奇点

// 加一条无向边，两个方向各存一条半边
void add_edge(ll u, ll v, ll id) {
    edge[cnt_edge].to = v; edge[cnt_edge].id = id;
    nxt[cnt_edge] = head[u];
    head[u] = cnt_edge; cnt_edge++;

    edge[cnt_edge].to = u; edge[cnt_edge].id = id;
    nxt[cnt_edge] = head[v];
    head[v] = cnt_edge; cnt_edge++;
}

// 检查第 e 条半边是否可走：它所属的无向边（含反向半边）还没走过
bool check_ok(ll e) {
    if (used[edge[e].id]) return false;
    if (used[edge[e ^ 1].id]) return false;
    return true;
}

// Hierholzer 迭代版：能走就走并压栈，走不动才把点记进出栈序列
void solve() {
    ll n, m;
    scanf("%lld %lld", &n, &m);
    for (ll i = 0; i < m; ++i) {
        ll a, b;
        scanf("%lld %lld", &a, &b);
        add_edge(a, b, i);
        deg[a]++; deg[b]++;
    }

    // 选起点：有奇点就从编号最大的奇点出发，否则取第一个有边的点
    ll start = 0;
    for (ll i = 1; i <= n; ++i)
        if (deg[i] % 2 == 1) start = i;
    if (start == 0)
        for (ll i = 1; i <= n; ++i)
            if (deg[i] > 0) { start = i; break; }
    if (start == 0) start = 1;   // 一条边都没有时兜底输出 1

    sta[top++] = start;
    while (top > 0) {
        ll u = sta[top - 1];     // 只看栈顶，不弹出
        ll e = head[u];
        while (e != -1 && !check_ok(e)) e = nxt[e];   // 找第一条可走的边
        if (e != -1) {
            used[edge[e].id] = true;   // 走掉这条边
            sta[top++] = edge[e].to;
        } else {
            top--;                     // 无路可走，这个点正式落进出栈序列
            ans[len_ans++] = u;
        }
    }

    // 出栈序列逆序输出才是欧拉路（起点在前，终点在后）
    for (ll i = len_ans - 1; i >= 0; --i)
        printf("%lld%c", ans[i], i == 0 ? '\n' : ' ');
}

int main() {
    for (ll i = 0; i < MAXN; ++i) head[i] = -1;
    solve();
    return 0;
}

【例题】一笔画问题

目录

题目描述

思路

参考代码