「Watchcow」看牛

形式化题目

给定无向图 $G=(V,E)$ ， $1\in V$ ， $|V|=N$ ， $|E|=M$ （允许自环与重边）。要求给出顶点序列

v_0,v_1,\dots,v_{2M},\quad v_0=v_{2M}=1,

使得把序列相邻两项看成一条有向弧后，这 $2M$ 条弧恰好是：每条无向边 $\{a,b\}$ 贡献弧 $a\to b$ 与 $b\to a$ 各一次。

换句话说，求一条从 $1$ 出发、回到 $1$ 、并且每条边正反两个方向各经过一次的闭合路径。

样例图（ $N=4$ ，边为 $1\!-\!2,\ 1\!-\!4,\ 2\!-\!3,\ 2\!-\!4,\ 3\!-\!4$ ）：

graph Watchcow {
  node [shape=circle, style=filled, fillcolor=white];
  rankdir=LR;
  1 -- 2;
  1 -- 4;
  2 -- 3;
  2 -- 4;
  3 -- 4;
}

图中每条边都要被走两遍（一去一回），所以答案有 $2M+1=11$ 个顶点。样例给出的是 1 2 3 4 2 1 4 3 2 4 1，但题目允许任意一种方案。

正解

思路

第一步：把"每条边正反各走一次"改写成"每条弧恰好用一次"。

输入一条无向边 $\{a,b\}$ 时，直接向有向图里插两条弧 $a\to b$ 和 $b\to a$ 。 $M$ 条边变成 $2M$ 条弧，“每条边两个方向各一次"就逐字变成"每条弧恰好使用一次”：

在有向图上求一条从 $1$ 出发、回到 $1$ 的欧拉回路。

这样改写的好处是：后面完全按有向图处理，不需要在遍历时反复判断"这条边是不是桥"。

第二步：确认一定有解，从而不必写可行性判断。

拆弧后，每个点 $v$ 的出度等于入度，都等于原图中的度数 $deg(v)$ ；所有带边的点又在同一个连通块里。这正是有向图存在欧拉回路的判据，所以从 $1$ 出发一定能走完所有弧并回到 $1$ 。

第三步：放弃 Fleury，改用 Hierholzer。

朴素思路"每步随便挑一条没走过的弧"可能走进死胡同——走进一个与剩余部分不连通的区域。Fleury 的修法是：除非无路可走，否则不走桥。但每步判桥要一次连通性检查，总计 $O(M(N+M))$ ，不可接受。

Hierholzer 换了个角度：一路走到底，走进死胡同就回溯，把剩下的圈缝进已有回路。

text

1
2
3
4
5dfs(v):
    while v 还有未使用的出弧 (v, u):
        标记该弧已用
        dfs(u)
    tour.append(v)          # v 的出边用光了，此刻 v 就是回路末尾

关键在于"出边用光的点可以立刻固定到回路末尾"：由于每个点入出度平衡，只要还有弧没用完，从死胡同里一定还能走回主干，于是这段闭合的圈可以整体插进正在构造的回路。所以走进死胡同从来不是错误，只是一个可以回退的局部结构。

第四步：递归改成迭代。

上面的递归深度最坏是 $O(M)$ （沿长链一路深入、一步也不回退）， $M=5\times10^4$ 时 Python 直接爆栈。把"尚未走完的路径前缀"放进显式栈：

python

1
2
3
4
5
6
7
8
9stack = [start]
tour = []                              # 已固定的回路后缀（逆序）
while stack:
    arc = head[stack[-1]]              # 栈顶 = 递归里的当前点 v
    if arc == NO_ARC:                  # v 的出边用光了
        tour.append(stack.pop())       # 等价于 dfs 返回前的 tour.append(v)
    else:
        head[stack[-1]] = nxt[arc]     # 摘掉这条弧 = 标记已用
        stack.append(to[arc])          # 顺着这条弧深入

两个实现要点：

"标记弧已用"就是摘链表头。 head[v] 同时充当" $v$ 还未使用的弧的链表"和 “已用标记”：摘掉之后 head 再也指不到它，正反两条弧各自只可能被用一次，不需要额外的 used 数组。
记录顺序是逆序。 出边用光就出栈的点是回路末尾的点，所以 tour[::-1] 才是答案。

样例推演。 用样例跑迭代替换版，看栈与答案序列如何演化：

步骤	本步动作	变化后的栈（底 → 顶）	已定下的序列（尾 → 头）
1	用弧 2: 1 -> 4	`[1, 4]`	`[]`
2	用弧 9: 4 -> 3	`[1, 4, 3]`	`[]`
3	用弧 8: 3 -> 4	`[1, 4, 3, 4]`	`[]`
4	用弧 7: 4 -> 2	`[1, 4, 3, 4, 2]`	`[]`
5	用弧 6: 2 -> 4	`[1, 4, 3, 4, 2, 4]`	`[]`
6	用弧 3: 4 -> 1	`[1, 4, 3, 4, 2, 4, 1]`	`[]`
…	…（继续用弧 0、4、5、1 走到 `[1, 4, 3, 4, 2, 4, 1, 2, 3, 2, 1]`）	…	…
11	出边用光，钉到答案末尾	`[]`	`[1]`
12	出边用光，钉到答案末尾	`[]`	`[1, 2]`
…	…（连续 11 次回退）	…	…
21	出边用光，钉到答案末尾	`[]`	`[1, 2, 3, 2, 1, 4, 2, 4, 3, 4, 1]`

前 10 步是一条不断深入的路径，栈正是这条前缀；第 11 步开始"出边用光"连续触发 11 次，栈整体回退，回退顺序恰好是回路从尾到头的顺序。把最后一列翻转，得到

text

11 4 3 4 2 4 1 2 3 2 1

它与 main.py 的实际输出一致：首尾都是 $1$ ，而且相邻点对恰好把 5 条边各走了两遍（ $2\times5+1=11$ 个数）。这个解和样例给出的解不同，但题目允许输出任意一种。

代码

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/**
 * 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-10 13:00
 * update_at: 2026-10-10 13:00
 */

// 蚂蚁的旅行：每条无向边拆成两条反向弧，求欧拉回路
#include <cstdio>
#include <vector>
using namespace std;

const int NO_ARC = -1; // 邻接链表结束标记

int n, m;
vector<int> head, nxt, to;

int main() {
    if (scanf("%d %d", &n, &m) != 2) {
        return 0;
    }
    // 弧 2i / 2i+1 是同一条边的两个方向：弧 arc 的起点是 to[arc^1]，终点是 to[arc]
    to.assign(2 * m, 0);
    for (int i = 0; i < 2 * m; i++) {
        scanf("%d", &to[i]);
    }
    nxt.assign(2 * m, NO_ARC);
    head.assign(n + 1, NO_ARC);
    for (int arc = 0; arc < 2 * m; arc++) {
        int v = to[arc ^ 1];
        nxt[arc] = head[v];
        head[v] = arc;
    }

    // 栈里存的是一条尚未走完的路径前缀；栈顶点没有出边了就钉到回路末尾
    vector<int> stk, tour;
    stk.push_back(1);
    while (!stk.empty()) {
        int u = stk.back();
        int arc = head[u];
        if (arc == NO_ARC) {
            tour.push_back(u);
            stk.pop_back();
        } else {
            head[u] = nxt[arc]; // 摘掉这条弧，保证每条边只用一次
            stk.push_back(to[arc]);
        }
    }

    for (int i = (int)tour.size() - 1; i >= 0; i--) {
        printf("%d", tour[i]);
        if (i) {
            printf("\n");
        }
    }
    return 0;
}

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#!/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-10-02 01:09
# update_at: 2026-10-04 11:42

import sys
from array import array

NO_ARC = -1  # 邻接链表结束标记；弧编号从 0 开始，所以只能用负数当空指针


def euler_circuit(nxt: array, to: array, head: array, start: int) -> list[int]:
    """从 start 出发逐条用掉弧，返回欧拉回路的顶点序列（逆序，需翻转后输出）。

    每条无向边拆成互为反向的两条有向弧，因此每个点入度 = 出度，
    有向图必有欧拉回路。栈里存的是一条尚未走完的路径前缀：
    栈顶点还有弧就从它继续往下走，一条弧都没有了就说明它的后继已经确定，
    可以立刻钉死在回路的末尾。
    """
    stack = [start]
    tour: list[int] = []
    while stack:
        arc = head[stack[-1]]
        if arc == NO_ARC:
            tour.append(stack.pop())  # 出边用光：这个点已经可以固定到回路末尾
        else:
            head[stack[-1]] = nxt[arc]  # 摘掉这条弧，保证正、反方向各只用一次
            stack.append(to[arc])
    return tour


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

    # 弧 2i / 2i+1 是同一条边的两个方向：弧 arc 的起点是 to[arc ^ 1]，终点是 to[arc]
    to = array('i', (next(data) for _ in range(2 * m)))
    nxt = array('i', [NO_ARC]) * (2 * m)
    head = array('i', [NO_ARC]) * (n + 1)
    for arc in range(2 * m):
        v = to[arc ^ 1]
        nxt[arc] = head[v]
        head[v] = arc

    tour = euler_circuit(nxt, to, head, 1)
    sys.stdout.write('\n'.join(map(str, tour[::-1])))


if __name__ == "__main__":
    solve()

复杂度

设 $N$ 为点数、 $M$ 为边数。

时间：读入建图 $O(N+M)$ ，Hierholzer 中每条弧恰好压栈一次、出栈一次， $O(N+M)$ ，输出 $2M+1$ 行 $O(M)$ ，合计 $O(N+M)$ 。
空间：链式前向星三个数组各 $O(N+M)$ ，栈与回路 $O(M)$ ，合计 $O(N+M)$ 。

总结

题目的"每条边正反各经过一次"等价于"每条弧恰好经过一次"，于是本题就是有向图欧拉回路模板。
拆弧后出度 = 入度自动成立，解一定存在，不需要可行性判断。
Hierholzer 用"随便走 + 回溯拼接"免掉了 Fleury 的判桥，把 $O(M(N+M))$ 降到 $O(N+M)$ 。
Python 实现必须把递归改成显式栈，并用"摘链表头"代替 used 数组；记录顺序要翻转。

图示解析

这张图串起本题从建模到得到答案的主线：

text

1
2
3
4
5
6
7
8
9无向图 (N 个点, M 条边)：每条边正、反方向各走一次
`- 建模：把每条无向边拆成两条有向弧，问题变成"每条弧恰好用一次"
   `- 关键观察：拆弧后每个点 出度 = 入度 = 原度数
      |- 有向图欧拉回路判据成立 → 一定有解，不需要可行性特判
      |- 放弃 Fleury（每步判桥 O(M(N+M))）
      `- Hierholzer：一路随便走，走进死胡同再回溯
         |- 递归版会 O(M) 层爆栈 → 改成显式栈
         |- "标记弧已用" = 从邻接链表头摘掉该弧
         `- 出边用光的点立刻钉到回路末尾 → tour 逆序 → 翻转输出 2M+1 个数

先看第一层如何把"每条边两个方向"翻译成"每条弧一次"，再顺着分支看平衡条件怎样保证解必定存在、Hierholzer 又怎样把"避桥"这个瓶颈彻底消掉，最后一步只是把记录顺序翻过来。

「Watchcow」 看牛

目录

形式化题目

正解

思路

代码

复杂度

总结

图示解析