送货

GitHub跳转原题关系图Canvas 关系图返回列表

检查固定起点的欧拉路条件后，按邻接点升序执行 Hierholzer 构造字典序最小路径。

OJ: shumeng

题目 ID: CSP201512D

难度:普及+/提高-

标签:欧拉路径图论贪心

日期: 2026-07-31 16:21

目录

  1. 形式化题目
  2. 思路
    1. 欧拉路的判定条件
    2. 字典序最小：邻接表升序
    3. Hierholzer 算法
  3. 代码
  4. 复杂度
  5. 总结

形式化题目

给定 nn 个点 mm 条边的无向图，从 11 号点出发，经过每条边恰好一次，输出字典序最小的顶点序列；若不存在这样的路径，输出 -1。

思路

“经过每条边恰好一次”就是经典的一笔画问题，等价于求欧拉路（非闭合）或欧拉回路。

欧拉路的判定条件

无向图存在欧拉路的充要条件是：图连通，且奇度顶点数为 00 或 22。

  • 奇度数为 00：存在欧拉回路，从任意点出发都行；
  • 奇度数为 22：存在欧拉路，且必须以其中一个奇度点为起点。

本题固定从 11 出发，所以若恰好有两个奇度点，11 必须是其中之一。

字典序最小：邻接表升序

若邻接表按终点编号升序排列，并总是优先走“当前编号最小的未用边”，那么欧拉路自然字典序最小。这是贪心思想：每步取最小的可行下一顶点。

Hierholzer 算法

用栈模拟递归过程，维护每个点当前扫描到的边：

  1. 从起点入栈；
  2. 栈顶点的边走完就出栈并记录该顶点；
  3. 否则走一条未用边，标记边已用，把另一端入栈。

最后把记录的顶点序列反转，就得到欧拉路径。注意还要验证生成的顶点数是否为 m+1m+1：若少于 m+1m+1，说明从 11 出发到达不了所有边，即图不连通，输出 -1。

代码

cpp
/**
 * 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-07-31 16:21
 * update_at: 2026-08-17 23:01
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;
const int MAXM = 100005;

struct Edge {
    int to; // 边的另一端
    int id; // 边的编号，用于标记是否已使用
};

// 邻接表按终点升序排序，保证 Hierholzer 走出的路径字典序最小。
bool compare_edge(const Edge &left, const Edge &right) {
    return left.to < right.to;
}

int n, m;
vector<Edge> graph[MAXN]; // 邻接表存无向图
int degree[MAXN];         // 每个点的度数
int used[MAXM];           // used[id] 标记第 id 条边是否已走过
int pointer[MAXN];        // 每个点当前扫描到第几条边
vector<int> stack_nodes;  // Hierholzer 的递归栈
vector<int> path;         // 最终欧拉路径的顶点序列（逆序记录）

// 判断是否存在从 1 出发、经过所有边恰好一次的欧拉路，并输出字典序最小的路径。
// 欧拉路存在条件：奇度点数为 0（欧拉回路）或 2（欧拉路）；
// 若为 2，起点 1 必须是其中一个奇度点。
bool euler_path_exists() {
    int odd_count = 0;
    for (int i = 1; i <= n; i++) {
        if (degree[i] % 2 == 1) odd_count++;
    }
    if (odd_count != 0 && odd_count != 2) return false;
    if (odd_count == 2 && degree[1] % 2 == 0) return false;
    return true;
}

// Hierholzer 算法：每次优先走当前编号最小的未用边，
// 走不动时把顶点压入 path，最后整体反转得到欧拉路。
void build_euler_path() {
    stack_nodes.push_back(1);
    while (!stack_nodes.empty()) {
        int u = stack_nodes.back();
        // 跳过已经使用过的边。
        while (pointer[u] < (int)graph[u].size() && used[graph[u][pointer[u]].id]) {
            pointer[u]++;
        }
        if (pointer[u] == (int)graph[u].size()) {
            // 当前点的边都走完了，回溯并记录顶点。
            path.push_back(u);
            stack_nodes.pop_back();
        } else {
            Edge edge = graph[u][pointer[u]++];
            used[edge.id] = 1;
            stack_nodes.push_back(edge.to);
        }
    }
}

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

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back((Edge){v, i});
        graph[v].push_back((Edge){u, i});
        degree[u]++;
        degree[v]++;
    }

    if (!euler_path_exists()) {
        cout << -1 << '\n';
        return 0;
    }

    for (int i = 1; i <= n; i++) {
        sort(graph[i].begin(), graph[i].end(), compare_edge);
    }

    build_euler_path();

    // 顶点数应为 m+1（每条边贡献一个顶点）；否则说明图不连通，无解。
    if ((int)path.size() != m + 1) {
        cout << -1 << '\n';
        return 0;
    }

    reverse(path.begin(), path.end());
    for (int i = 0; i < (int)path.size(); i++) {
        if (i > 0) cout << ' ';
        cout << path[i];
    }
    cout << '\n';
    return 0;
}

复杂度

  • 时间：邻接表排序 O(mlog⁡m)O(m\log m)，Hierholzer 每个点和边各访问常数次，O(n+m)O(n+m)。
  • 空间：邻接表与栈，O(n+m)O(n+m)。

总结

欧拉路的奇度条件只保证“可能性”，实际构造后仍需检查是否用到了所有边，以排除图不连通的情况。无向边要按编号标记，避免同一对顶点间的边被重复走。固定起点加邻接表升序，就能直接得到字典序最小解。