オイラー路(Eulerian Trail)
(graph/eulerian_trail.cpp)

• View this file on GitHub
• Last update: 2026-03-08 22:25:54+09:00

説明

有向グラフまたは無向グラフの Eulerian trail / circuit を 1 つ構成する。 辺をちょうど 1 回ずつ通る頂点列と辺番号列を返す。

できること

• EulerianTrail<false> g(n) 頂点数 n の無向グラフを作る
• EulerianTrail<true> g(n) 頂点数 n の有向グラフを作る
• int add_edge(int from, int to) 辺を追加し、辺番号を返す
• Result solve() Eulerian trail が存在すれば構成を返す。存在しないとき exists == false

Result は次を持つ。

• bool exists Eulerian trail が存在するか
• vector<int> vertices 通る頂点列。長さは M + 1
• vector<int> edge_ids 通る辺番号列。長さは M

使い方

全辺を add_edge で追加し、solve() を呼ぶ。 vertices[i] -> vertices[i + 1] に対応する辺番号が edge_ids[i] に入る。

実装上の補足

Hierholzer 法で構成する。 計算量は $O(N + M)$。

Verified with

• test/yosupo_eulerian_trail_directed.test.cpp
• test/yosupo_eulerian_trail_undirected.test.cpp

Code

template<bool directed>
struct EulerianTrail {
    struct Edge {
        int from, to;
    };

    struct Result {
        bool exists;
        vector<int> vertices;
        vector<int> edge_ids;
    };

    int n;
    vector<Edge> edges;
    vector<vector<pair<int, int>>> g;

    explicit EulerianTrail(int n) : n(n), g(n) {}

    int add_edge(int from, int to) {
        int id = (int)edges.size();
        edges.push_back({from, to});
        g[from].push_back({to, id});
        if constexpr (!directed) g[to].push_back({from, id});
        return id;
    }

    Result solve() const {
        int m = edges.size();
        if (m == 0) {
            return {true, {0}, {}};
        }

        vector<int> indeg(n), outdeg(n), deg(n);
        for (auto&& e : edges) {
            ++outdeg[e.from];
            ++indeg[e.to];
            ++deg[e.from];
            ++deg[e.to];
        }

        int start = -1, plus = 0, minus = 0;
        if constexpr (directed) {
            for (int v = 0; v < n; ++v) {
                int diff = outdeg[v] - indeg[v];
                if (diff == 1) {
                    start = v;
                    ++plus;
                } else if (diff == -1) {
                    ++minus;
                } else if (diff != 0) {
                    return {false, {}, {}};
                }
            }
            if (!((plus == 1 && minus == 1) || (plus == 0 && minus == 0))) {
                return {false, {}, {}};
            }
            if (start == -1) {
                for (int v = 0; v < n; ++v) {
                    if (outdeg[v] > 0) {
                        start = v;
                        break;
                    }
                }
            }
        } else {
            int odd = 0;
            for (int v = 0; v < n; ++v) {
                if (deg[v] & 1) {
                    start = v;
                    ++odd;
                }
            }
            if (!(odd == 0 || odd == 2)) return {false, {}, {}};
            if (start == -1) {
                for (int v = 0; v < n; ++v) {
                    if (deg[v] > 0) {
                        start = v;
                        break;
                    }
                }
            }
        }

        vector<int> ptr(n), used(m);
        vector<int> st_v{start}, st_e{-1};
        vector<int> vs, es;
        while (!st_v.empty()) {
            int v = st_v.back();
            while (ptr[v] < (int)g[v].size() && used[g[v][ptr[v]].second]) ++ptr[v];
            if (ptr[v] == (int)g[v].size()) {
                vs.push_back(v);
                st_v.pop_back();
                int id = st_e.back();
                st_e.pop_back();
                if (id != -1) es.push_back(id);
                continue;
            }
            auto [to, id] = g[v][ptr[v]++];
            if (used[id]) continue;
            used[id] = 1;
            st_v.push_back(to);
            st_e.push_back(id);
        }

        if ((int)es.size() != m) return {false, {}, {}};
        reverse(vs.begin(), vs.end());
        reverse(es.begin(), es.end());
        return {true, vs, es};
    }
};

/**
 * @brief オイラー路(Eulerian Trail)
 */

#line 1 "graph/eulerian_trail.cpp"
template<bool directed>
struct EulerianTrail {
    struct Edge {
        int from, to;
    };

    struct Result {
        bool exists;
        vector<int> vertices;
        vector<int> edge_ids;
    };

    int n;
    vector<Edge> edges;
    vector<vector<pair<int, int>>> g;

    explicit EulerianTrail(int n) : n(n), g(n) {}

    int add_edge(int from, int to) {
        int id = (int)edges.size();
        edges.push_back({from, to});
        g[from].push_back({to, id});
        if constexpr (!directed) g[to].push_back({from, id});
        return id;
    }

    Result solve() const {
        int m = edges.size();
        if (m == 0) {
            return {true, {0}, {}};
        }

        vector<int> indeg(n), outdeg(n), deg(n);
        for (auto&& e : edges) {
            ++outdeg[e.from];
            ++indeg[e.to];
            ++deg[e.from];
            ++deg[e.to];
        }

        int start = -1, plus = 0, minus = 0;
        if constexpr (directed) {
            for (int v = 0; v < n; ++v) {
                int diff = outdeg[v] - indeg[v];
                if (diff == 1) {
                    start = v;
                    ++plus;
                } else if (diff == -1) {
                    ++minus;
                } else if (diff != 0) {
                    return {false, {}, {}};
                }
            }
            if (!((plus == 1 && minus == 1) || (plus == 0 && minus == 0))) {
                return {false, {}, {}};
            }
            if (start == -1) {
                for (int v = 0; v < n; ++v) {
                    if (outdeg[v] > 0) {
                        start = v;
                        break;
                    }
                }
            }
        } else {
            int odd = 0;
            for (int v = 0; v < n; ++v) {
                if (deg[v] & 1) {
                    start = v;
                    ++odd;
                }
            }
            if (!(odd == 0 || odd == 2)) return {false, {}, {}};
            if (start == -1) {
                for (int v = 0; v < n; ++v) {
                    if (deg[v] > 0) {
                        start = v;
                        break;
                    }
                }
            }
        }

        vector<int> ptr(n), used(m);
        vector<int> st_v{start}, st_e{-1};
        vector<int> vs, es;
        while (!st_v.empty()) {
            int v = st_v.back();
            while (ptr[v] < (int)g[v].size() && used[g[v][ptr[v]].second]) ++ptr[v];
            if (ptr[v] == (int)g[v].size()) {
                vs.push_back(v);
                st_v.pop_back();
                int id = st_e.back();
                st_e.pop_back();
                if (id != -1) es.push_back(id);
                continue;
            }
            auto [to, id] = g[v][ptr[v]++];
            if (used[id]) continue;
            used[id] = 1;
            st_v.push_back(to);
            st_e.push_back(id);
        }

        if ((int)es.size() != m) return {false, {}, {}};
        reverse(vs.begin(), vs.end());
        reverse(es.begin(), es.end());
        return {true, vs, es};
    }
};

/**
 * @brief オイラー路(Eulerian Trail)
 */

Back to top page