欧拉回路与欧拉路径 (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 + 圈套圈思想，后序遍历回溯时将边/顶点压栈，最后逆序输出。

[!WARNING] 当前弧优化 (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;
    }
};