欧拉回路与欧拉路径 (Eulerian Circuit & Path)¶

欧拉路径 (Eulerian Trail/Path)：通过图中每条边恰好一次的路径（一笔画问题）。
欧拉回路 (Eulerian Circuit)：起点与终点相同的欧拉路径。

存在性判定定理¶

图必须保证所有非零度顶点处于同一连通块中（孤立点可忽略）。

1. 无向图¶

欧拉回路：所有顶点的度数均为偶数。
欧拉路径：恰有 \(0\) 个或 \(2\) 个顶点的度数为奇数。若有 \(2\) 个奇度点，则它们分别为路径的起点和终点。

2. 有向图¶

欧拉回路：对所有顶点，其入度等于出度（\(\text{in}(u) = \text{out}(u)\)）。
欧拉路径：
要么所有顶点 \(\text{in}(u) = \text{out}(u)\)（此时为欧拉回路）；
要么恰有一个顶点满足 \(\text{out}(u) - \text{in}(u) = 1\)（作为起点），恰有一个顶点满足 \(\text{in}(v) - \text{out}(v) = 1\)（作为终点），其余所有顶点满足 \(\text{in}(w) = \text{out}(w)\)。

Hierholzer 算法 (求具体欧拉路径)¶

Hierholzer 算法基于 DFS + 圈套圈思想，后序遍历回溯时将边/顶点压栈，最后逆序输出。

当前弧优化 (Crucial!)

在 DFS 递归过程中，遍历过的边必须被永久跳过或删除。若每次从头遍历邻接表，在重边密集图或菊花图上会导致复杂度退化为 \(\mathcal{O}(E^2)\) 导致 TLE。必须使用当前弧下标引用递增或 pop_back 保证每条边仅被访问常数次，达到严格 \(\mathcal{O}(V + E)\)。

1. 有向图欧拉路径¶

#include <vector>
#include <algorithm>

struct DirectedEuler {
    int n;
    std::vector<std::vector<int>> adj;
    std::vector<int> in_deg, out_deg;
    std::vector<int> cur_edge; // 当前弧优化
    std::vector<int> path;     // 记录顶点路径

    DirectedEuler(int n) : n(n), adj(n), in_deg(n, 0), out_deg(n, 0), cur_edge(n, 0) {}

    void add_edge(int u, int v) {
        adj[u].push_back(v);
        out_deg[u]++;
        in_deg[v]++;
    }

    void dfs(int u) {
        while (cur_edge[u] < (int)adj[u].size()) {
            int v = adj[u][cur_edge[u]++];
            dfs(v);
        }
        path.push_back(u); // 后序压栈
    }

    // 若存在欧拉路径，返回顶点序列；否则返回空
    std::vector<int> get_euler_path() {
        // 若要求字典序最小，需提前对每个 adj[u] 排序
        for (int i = 0; i < n; ++i) {
            std::sort(adj[i].begin(), adj[i].end());
        }

        int start_node = 0;
        int out_minus_in = 0, in_minus_out = 0;

        // 寻找有向路径的起点
        for (int i = 0; i < n; ++i) {
            if (out_deg[i] - in_deg[i] == 1) {
                start_node = i;
                out_minus_in++;
            } else if (in_deg[i] - out_deg[i] == 1) {
                in_minus_out++;
            } else if (in_deg[i] != out_deg[i]) {
                return {}; // 度数不满足
            }
            if (out_deg[i] > 0 && out_minus_in == 0) {
                start_node = i; // 默认若度数全平衡，任选有出边的点作为起点
            }
        }

        if (!((out_minus_in == 1 && in_minus_out == 1) || (out_minus_in == 0 && in_minus_out == 0))) {
            return {};
        }

        dfs(start_node);
        std::reverse(path.begin(), path.end());
        return path;
    }
};

2. 无向图欧拉路径 (带边访问标记)¶

无向图的一条边在邻接表中存为两条反向边，需用全局 vis_edge 标记整条无向边是否已用过。

struct UndirectedEuler {
    struct Edge { int to, id; };
    int n, edge_cnt = 0;
    std::vector<std::vector<Edge>> adj;
    std::vector<int> deg;
    std::vector<int> cur_edge;
    std::vector<bool> vis_edge;
    std::vector<int> path;

    UndirectedEuler(int n) : n(n), adj(n), deg(n, 0), cur_edge(n, 0) {}

    void add_edge(int u, int v) {
        int id = edge_cnt++;
        adj[u].push_back({v, id});
        adj[v].push_back({u, id});
        deg[u]++; deg[v]++;
    }

    void dfs(int u) {
        while (cur_edge[u] < (int)adj[u].size()) {
            auto [v, id] = adj[u][cur_edge[u]++];
            if (vis_edge[id]) continue;
            vis_edge[id] = true;
            dfs(v);
        }
        path.push_back(u);
    }

    std::vector<int> get_euler_path() {
        vis_edge.assign(edge_cnt, false);
        int odd_cnt = 0, start_node = -1;

        for (int i = 0; i < n; ++i) {
            if (deg[i] % 2 != 0) {
                odd_cnt++;
                if (start_node == -1) start_node = i;
            }
            if (deg[i] > 0 && start_node == -1) {
                start_node = i;
            }
        }

        if (odd_cnt != 0 && odd_cnt != 2) return {};
        if (start_node == -1) return {};

        dfs(start_node);
        std::reverse(path.begin(), path.end());
        return path;
    }
};

LeetCode 经典真题精选与题解提示¶

LeetCode 332 - 重新安排行程 (Reconstruct Itinerary) 困难
提示

字典序最小有向图欧拉路径标杆。
- 机场作为顶点，机票作为有向边；必须从 "JFK" 出发用尽所有机票；
- 使用优先队列（最小堆）或排序邻接表维护字典序最小出边；
- 利用 Hierholzer 算法 DFS 后序入栈（回溯时 path.push_back），最后将路径反转即可得到自然字典序最小的欧拉路径。
LeetCode 753 - 破解保险箱 (Cracking the Safe) 困难
提示

De Bruijn 序列转化为欧拉回路。
- 寻找包含所有长度为 \(n\) 的 \(k\) 进制序列的最短环形字符串；
- 将所有长度为 \(n - 1\) 的串作为图的节点，共有 \(k^{n-1}\) 个节点；
- 从节点 \(u\) 追加字符 \(x \in [0, k-1]\) 转移到新节点 \(v = (u \times k + x) \pmod{k^{n-1}}\) 作为有向边；每个节点入度出度均为 \(k\)，天然存在欧拉回路，遍历每条边一次输出对应的 De Bruijn 序列。
LeetCode 2097 - 合法重新排列数对 (Valid Arrangement of Pairs) 困难
提示

大范围数对欧拉路径。
- 给定 \(10^5\) 个数对 \([start, end]\)，重排使其首尾相接：天然对应有向图求欧拉路径；
- 离散化或用 unordered_map<int, vector<int>> 建图，统计出度与入度；
- 找到唯一的起点（满足 \(out - in == 1\) 的节点；若全平衡则任选起点）；
- 使用当前弧优化的 Hierholzer 算法在 \(\mathcal{O}(V + E)\) 内输出边路径。