Eulerian Trail
(graph/eulerian_trail.hpp)

View this file on GitHub
Last update: 2026-08-13 01:41:40+09:00
Include: #include "graph/eulerian_trail.hpp"

Overview

An Eulerian trail uses every active edge exactly once. This header implements iterative Hierholzer traversals for both directed and undirected graphs and returns the original edge IDs alongside the visited vertices.

Parallel edges and self-loops are supported. Inactive edges are ignored.

Graph Orientation

Use directed_eulerian_trail with graphs built by add_directed_edge, and undirected_eulerian_trail with graphs built by add_edge. Mixing directed and undirected edge representations in one call is not supported.

API

struct EulerianTrail {
    std::vector<int> vertices;
    std::vector<int> edge_ids;

    int edge_count() const;
    bool is_circuit() const;
};

template <class T>
std::optional<EulerianTrail> directed_eulerian_trail(
    const Graph<T>& graph,
    int start = -1
);

template <class T>
std::optional<EulerianTrail> undirected_eulerian_trail(
    const Graph<T>& graph,
    int start = -1
);

Interface	Description	Complexity
`vertices`	Trail vertices; for `M` used edges, contains `M + 1` vertices unless the graph itself has no vertices.	–
`edge_ids`	Active edge IDs in traversal order.	–
`edge_count()`	Number of edges in the trail.	$O(1)$
`is_circuit()`	Whether the trail is closed. An empty-graph trail is considered closed.	$O(1)$
`directed_eulerian_trail(graph, start)`	Finds a direction-respecting trail, if one exists.	$O(N + M)$
`undirected_eulerian_trail(graph, start)`	Finds an undirected trail, if one exists.	$O(N + M)$

The default start == -1 chooses a valid start automatically. Supplying a vertex forces the trail to start there; the function returns std::nullopt if an Eulerian trail exists only from another vertex. Invalid nonnegative start indices are rejected by an assertion.

For a graph with vertices but no active edges, the automatically selected trail contains vertex 0 and no edges. A forced start produces that one-vertex trail instead. For a graph with no vertices, both returned sequences are empty.

The functions check degree conditions and confirm that Hierholzer’s traversal used every active edge, which also detects disconnected edge-bearing parts. The graph is not mutated.

Example

#include "graph/eulerian_trail.hpp"
#include "graph/graph.hpp"

#include <iostream>

int main() {
    m1une::graph::Graph<> graph(3);
    graph.add_directed_edge(0, 1);
    graph.add_directed_edge(1, 2);
    graph.add_directed_edge(2, 0);

    auto trail = m1une::graph::directed_eulerian_trail(graph);
    std::cout << trail->is_circuit() << "\n";  // 1
    for (int edge_id : trail->edge_ids) std::cout << edge_id << " ";
    std::cout << "\n";
}

Depends on

Graph (graph/graph.hpp)

Required by

Verified with

Code

#ifndef M1UNE_GRAPH_EULERIAN_TRAIL_HPP
#define M1UNE_GRAPH_EULERIAN_TRAIL_HPP 1

#include <algorithm>
#include <cassert>
#include <optional>
#include <utility>
#include <vector>

#include "graph.hpp"

namespace m1une {
namespace graph {

struct EulerianTrail {
    std::vector<int> vertices;
    std::vector<int> edge_ids;

    int edge_count() const {
        return int(edge_ids.size());
    }

    bool is_circuit() const {
        return vertices.empty() || vertices.front() == vertices.back();
    }
};

namespace internal {

template <class T>
std::optional<EulerianTrail> hierholzer(
    const Graph<T>& graph,
    int start,
    int active_edge_count
) {
    EulerianTrail result;
    if (active_edge_count == 0) {
        if (start != -1) result.vertices.push_back(start);
        return result;
    }

    assert(0 <= start && start < graph.size());
    std::vector<char> used(graph.edge_count(), false);
    std::vector<int> cursor(graph.size(), 0);
    std::vector<int> vertex_stack(1, start);
    std::vector<int> incoming_edge_stack(1, -1);
    std::vector<int> reversed_vertices;
    std::vector<int> reversed_edges;
    reversed_vertices.reserve(active_edge_count + 1);
    reversed_edges.reserve(active_edge_count);

    while (!vertex_stack.empty()) {
        const int vertex = vertex_stack.back();
        while (cursor[vertex] < int(graph[vertex].size())) {
            const Edge<T>& edge = graph[vertex][cursor[vertex]];
            if (edge.alive && !used[edge.id]) break;
            cursor[vertex]++;
        }

        if (cursor[vertex] < int(graph[vertex].size())) {
            const Edge<T>& edge = graph[vertex][cursor[vertex]++];
            used[edge.id] = true;
            vertex_stack.push_back(edge.to);
            incoming_edge_stack.push_back(edge.id);
            continue;
        }

        reversed_vertices.push_back(vertex);
        const int incoming_edge = incoming_edge_stack.back();
        if (incoming_edge != -1) reversed_edges.push_back(incoming_edge);
        vertex_stack.pop_back();
        incoming_edge_stack.pop_back();
    }

    if (int(reversed_edges.size()) != active_edge_count) return std::nullopt;
    std::reverse(reversed_vertices.begin(), reversed_vertices.end());
    std::reverse(reversed_edges.begin(), reversed_edges.end());
    result.vertices = std::move(reversed_vertices);
    result.edge_ids = std::move(reversed_edges);
    return result;
}

template <class T>
std::vector<int> edge_incidence_count(const Graph<T>& graph) {
    std::vector<int> count(graph.edge_count(), 0);
    for (int vertex = 0; vertex < graph.size(); vertex++) {
        for (const Edge<T>& edge : graph[vertex]) {
            if (!edge.alive) continue;
            assert(0 <= edge.id && edge.id < graph.edge_count());
            count[edge.id]++;
        }
    }
    return count;
}

}  // namespace internal

template <class T>
std::optional<EulerianTrail> directed_eulerian_trail(
    const Graph<T>& graph,
    int start = -1
) {
    assert(start == -1 || (0 <= start && start < graph.size()));
    const int n = graph.size();
    std::vector<int> incidence = internal::edge_incidence_count(graph);
    std::vector<int> in_degree(n, 0);
    std::vector<int> out_degree(n, 0);
    int active_edge_count = 0;
    for (int vertex = 0; vertex < n; vertex++) {
        for (const Edge<T>& edge : graph[vertex]) {
            if (!edge.alive) continue;
            out_degree[vertex]++;
            in_degree[edge.to]++;
        }
    }
    for (int count : incidence) {
        if (count == 0) continue;
        assert(count == 1);
        active_edge_count++;
    }

    int required_start = -1;
    int required_end = -1;
    for (int vertex = 0; vertex < n; vertex++) {
        const int difference = out_degree[vertex] - in_degree[vertex];
        if (difference == 1) {
            if (required_start != -1) return std::nullopt;
            required_start = vertex;
        } else if (difference == -1) {
            if (required_end != -1) return std::nullopt;
            required_end = vertex;
        } else if (difference != 0) {
            return std::nullopt;
        }
    }
    if ((required_start == -1) != (required_end == -1)) return std::nullopt;

    int chosen_start = start;
    if (active_edge_count == 0) {
        if (chosen_start == -1 && n > 0) chosen_start = 0;
        return internal::hierholzer(graph, chosen_start, 0);
    }
    if (required_start != -1) {
        if (chosen_start != -1 && chosen_start != required_start) return std::nullopt;
        chosen_start = required_start;
    } else if (chosen_start == -1) {
        for (int vertex = 0; vertex < n; vertex++) {
            if (out_degree[vertex] > 0) {
                chosen_start = vertex;
                break;
            }
        }
    } else if (out_degree[chosen_start] == 0) {
        return std::nullopt;
    }
    return internal::hierholzer(graph, chosen_start, active_edge_count);
}

template <class T>
std::optional<EulerianTrail> undirected_eulerian_trail(
    const Graph<T>& graph,
    int start = -1
) {
    assert(start == -1 || (0 <= start && start < graph.size()));
    const int n = graph.size();
    std::vector<int> incidence = internal::edge_incidence_count(graph);
    std::vector<int> degree(n, 0);
    int active_edge_count = 0;
    for (int vertex = 0; vertex < n; vertex++) {
        for (const Edge<T>& edge : graph[vertex]) {
            if (edge.alive) degree[vertex]++;
        }
    }
    for (int count : incidence) {
        if (count == 0) continue;
        assert(count == 2);
        active_edge_count++;
    }

    std::vector<int> odd;
    for (int vertex = 0; vertex < n; vertex++) {
        if (degree[vertex] & 1) odd.push_back(vertex);
    }
    if (!odd.empty() && odd.size() != 2) return std::nullopt;

    int chosen_start = start;
    if (active_edge_count == 0) {
        if (chosen_start == -1 && n > 0) chosen_start = 0;
        return internal::hierholzer(graph, chosen_start, 0);
    }
    if (odd.size() == 2) {
        if (chosen_start != -1 && chosen_start != odd[0] && chosen_start != odd[1]) {
            return std::nullopt;
        }
        if (chosen_start == -1) chosen_start = odd[0];
    } else if (chosen_start == -1) {
        for (int vertex = 0; vertex < n; vertex++) {
            if (degree[vertex] > 0) {
                chosen_start = vertex;
                break;
            }
        }
    } else if (degree[chosen_start] == 0) {
        return std::nullopt;
    }
    return internal::hierholzer(graph, chosen_start, active_edge_count);
}

}  // namespace graph
}  // namespace m1une

#endif  // M1UNE_GRAPH_EULERIAN_TRAIL_HPP

#line 1 "graph/eulerian_trail.hpp"



#include <algorithm>
#include <cassert>
#include <optional>
#include <utility>
#include <vector>

#line 1 "graph/graph.hpp"



#include <array>
#line 8 "graph/graph.hpp"

namespace m1une {
namespace graph {

template <class T = int>
struct Edge {
    using cost_type = T;

    int from;
    int to;
    T cost;
    int id;
    bool alive;

    Edge() : from(-1), to(-1), cost(T()), id(-1), alive(true) {}
    Edge(int from_, int to_, T cost_ = T(1), int id_ = -1, bool alive_ = true)
        : from(from_), to(to_), cost(cost_), id(id_), alive(alive_) {}

    int other(int v) const {
        assert(v == from || v == to);
        return from ^ to ^ v;
    }
};

template <class T = int>
struct Graph {
    using edge_type = Edge<T>;
    using cost_type = T;

   private:
    struct EdgePositions {
        std::array<std::pair<int, int>, 2> value{};
        int size = 0;

        void push_back(std::pair<int, int> position) {
            assert(size < 2);
            value[size++] = position;
        }
    };

    int _n;
    int _edge_count;
    std::vector<std::vector<edge_type>> _g;
    std::vector<EdgePositions> _edge_positions;

   public:
    Graph() : _n(0), _edge_count(0) {}
    explicit Graph(int n) : _n(n), _edge_count(0), _g(n) {
        assert(0 <= n);
    }

    int size() const {
        return _n;
    }

    bool empty() const {
        return _n == 0;
    }

    int edge_count() const {
        return _edge_count;
    }

    int add_vertex() {
        _g.emplace_back();
        return _n++;
    }

    int add_directed_edge(int from, int to, T cost = T(1)) {
        assert(0 <= from && from < _n);
        assert(0 <= to && to < _n);
        int id = _edge_count++;
        int idx = int(_g[from].size());
        _g[from].push_back(edge_type(from, to, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({from, idx});
        return id;
    }

    int add_edge(int u, int v, T cost = T(1)) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        int id = _edge_count++;
        int u_idx = int(_g[u].size());
        _g[u].push_back(edge_type(u, v, cost, id));
        int v_idx = int(_g[v].size());
        _g[v].push_back(edge_type(v, u, cost, id));
        _edge_positions.emplace_back();
        _edge_positions.back().push_back({u, u_idx});
        _edge_positions.back().push_back({v, v_idx});
        return id;
    }

    void set_edge_alive(int id, bool alive) {
        assert(0 <= id && id < _edge_count);
        for (int i = 0; i < _edge_positions[id].size; ++i) {
            auto [v, idx] = _edge_positions[id].value[i];
            _g[v][idx].alive = alive;
        }
    }

    void erase_edge(int id) {
        set_edge_alive(id, false);
    }

    void revive_edge(int id) {
        set_edge_alive(id, true);
    }

    bool is_edge_alive(int id) const {
        assert(0 <= id && id < _edge_count);
        assert(_edge_positions[id].size != 0);
        auto [v, idx] = _edge_positions[id].value[0];
        return _g[v][idx].alive;
    }

    const std::vector<edge_type>& operator[](int v) const {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    std::vector<edge_type>& operator[](int v) {
        assert(0 <= v && v < _n);
        return _g[v];
    }

    const std::vector<std::vector<edge_type>>& adjacency() const {
        return _g;
    }

    std::vector<std::vector<edge_type>>& adjacency() {
        return _g;
    }

    std::vector<edge_type> edges(bool include_inactive = false) const {
        std::vector<edge_type> result;
        result.reserve(_edge_count);
        std::vector<char> used(_edge_count, false);
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                if (!include_inactive && !e.alive) continue;
                if (0 <= e.id && e.id < _edge_count) {
                    if (used[e.id]) continue;
                    used[e.id] = true;
                }
                result.push_back(e);
            }
        }
        return result;
    }

    Graph reversed() const {
        Graph result(_n);
        result._edge_count = _edge_count;
        result._edge_positions.assign(_edge_count, {});
        for (int v = 0; v < _n; v++) {
            for (const auto& e : _g[v]) {
                int idx = int(result._g[e.to].size());
                result._g[e.to].push_back(edge_type(e.to, e.from, e.cost, e.id, e.alive));
                if (0 <= e.id && e.id < _edge_count) result._edge_positions[e.id].push_back({e.to, idx});
            }
        }
        return result;
    }
};

}  // namespace graph
}  // namespace m1une


#line 11 "graph/eulerian_trail.hpp"

namespace m1une {
namespace graph {

struct EulerianTrail {
    std::vector<int> vertices;
    std::vector<int> edge_ids;

    int edge_count() const {
        return int(edge_ids.size());
    }

    bool is_circuit() const {
        return vertices.empty() || vertices.front() == vertices.back();
    }
};

namespace internal {

template <class T>
std::optional<EulerianTrail> hierholzer(
    const Graph<T>& graph,
    int start,
    int active_edge_count
) {
    EulerianTrail result;
    if (active_edge_count == 0) {
        if (start != -1) result.vertices.push_back(start);
        return result;
    }

    assert(0 <= start && start < graph.size());
    std::vector<char> used(graph.edge_count(), false);
    std::vector<int> cursor(graph.size(), 0);
    std::vector<int> vertex_stack(1, start);
    std::vector<int> incoming_edge_stack(1, -1);
    std::vector<int> reversed_vertices;
    std::vector<int> reversed_edges;
    reversed_vertices.reserve(active_edge_count + 1);
    reversed_edges.reserve(active_edge_count);

    while (!vertex_stack.empty()) {
        const int vertex = vertex_stack.back();
        while (cursor[vertex] < int(graph[vertex].size())) {
            const Edge<T>& edge = graph[vertex][cursor[vertex]];
            if (edge.alive && !used[edge.id]) break;
            cursor[vertex]++;
        }

        if (cursor[vertex] < int(graph[vertex].size())) {
            const Edge<T>& edge = graph[vertex][cursor[vertex]++];
            used[edge.id] = true;
            vertex_stack.push_back(edge.to);
            incoming_edge_stack.push_back(edge.id);
            continue;
        }

        reversed_vertices.push_back(vertex);
        const int incoming_edge = incoming_edge_stack.back();
        if (incoming_edge != -1) reversed_edges.push_back(incoming_edge);
        vertex_stack.pop_back();
        incoming_edge_stack.pop_back();
    }

    if (int(reversed_edges.size()) != active_edge_count) return std::nullopt;
    std::reverse(reversed_vertices.begin(), reversed_vertices.end());
    std::reverse(reversed_edges.begin(), reversed_edges.end());
    result.vertices = std::move(reversed_vertices);
    result.edge_ids = std::move(reversed_edges);
    return result;
}

template <class T>
std::vector<int> edge_incidence_count(const Graph<T>& graph) {
    std::vector<int> count(graph.edge_count(), 0);
    for (int vertex = 0; vertex < graph.size(); vertex++) {
        for (const Edge<T>& edge : graph[vertex]) {
            if (!edge.alive) continue;
            assert(0 <= edge.id && edge.id < graph.edge_count());
            count[edge.id]++;
        }
    }
    return count;
}

}  // namespace internal

template <class T>
std::optional<EulerianTrail> directed_eulerian_trail(
    const Graph<T>& graph,
    int start = -1
) {
    assert(start == -1 || (0 <= start && start < graph.size()));
    const int n = graph.size();
    std::vector<int> incidence = internal::edge_incidence_count(graph);
    std::vector<int> in_degree(n, 0);
    std::vector<int> out_degree(n, 0);
    int active_edge_count = 0;
    for (int vertex = 0; vertex < n; vertex++) {
        for (const Edge<T>& edge : graph[vertex]) {
            if (!edge.alive) continue;
            out_degree[vertex]++;
            in_degree[edge.to]++;
        }
    }
    for (int count : incidence) {
        if (count == 0) continue;
        assert(count == 1);
        active_edge_count++;
    }

    int required_start = -1;
    int required_end = -1;
    for (int vertex = 0; vertex < n; vertex++) {
        const int difference = out_degree[vertex] - in_degree[vertex];
        if (difference == 1) {
            if (required_start != -1) return std::nullopt;
            required_start = vertex;
        } else if (difference == -1) {
            if (required_end != -1) return std::nullopt;
            required_end = vertex;
        } else if (difference != 0) {
            return std::nullopt;
        }
    }
    if ((required_start == -1) != (required_end == -1)) return std::nullopt;

    int chosen_start = start;
    if (active_edge_count == 0) {
        if (chosen_start == -1 && n > 0) chosen_start = 0;
        return internal::hierholzer(graph, chosen_start, 0);
    }
    if (required_start != -1) {
        if (chosen_start != -1 && chosen_start != required_start) return std::nullopt;
        chosen_start = required_start;
    } else if (chosen_start == -1) {
        for (int vertex = 0; vertex < n; vertex++) {
            if (out_degree[vertex] > 0) {
                chosen_start = vertex;
                break;
            }
        }
    } else if (out_degree[chosen_start] == 0) {
        return std::nullopt;
    }
    return internal::hierholzer(graph, chosen_start, active_edge_count);
}

template <class T>
std::optional<EulerianTrail> undirected_eulerian_trail(
    const Graph<T>& graph,
    int start = -1
) {
    assert(start == -1 || (0 <= start && start < graph.size()));
    const int n = graph.size();
    std::vector<int> incidence = internal::edge_incidence_count(graph);
    std::vector<int> degree(n, 0);
    int active_edge_count = 0;
    for (int vertex = 0; vertex < n; vertex++) {
        for (const Edge<T>& edge : graph[vertex]) {
            if (edge.alive) degree[vertex]++;
        }
    }
    for (int count : incidence) {
        if (count == 0) continue;
        assert(count == 2);
        active_edge_count++;
    }

    std::vector<int> odd;
    for (int vertex = 0; vertex < n; vertex++) {
        if (degree[vertex] & 1) odd.push_back(vertex);
    }
    if (!odd.empty() && odd.size() != 2) return std::nullopt;

    int chosen_start = start;
    if (active_edge_count == 0) {
        if (chosen_start == -1 && n > 0) chosen_start = 0;
        return internal::hierholzer(graph, chosen_start, 0);
    }
    if (odd.size() == 2) {
        if (chosen_start != -1 && chosen_start != odd[0] && chosen_start != odd[1]) {
            return std::nullopt;
        }
        if (chosen_start == -1) chosen_start = odd[0];
    } else if (chosen_start == -1) {
        for (int vertex = 0; vertex < n; vertex++) {
            if (degree[vertex] > 0) {
                chosen_start = vertex;
                break;
            }
        }
    } else if (degree[chosen_start] == 0) {
        return std::nullopt;
    }
    return internal::hierholzer(graph, chosen_start, active_edge_count);
}

}  // namespace graph
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Eulerian Trail
(graph/eulerian_trail.hpp)

Overview

Graph Orientation

API

Example

Depends on

Required by

Verified with

Code

Eulerian Trail (graph/eulerian_trail.hpp)

Overview

Graph Orientation

API

Example

Depends on

Required by

Verified with

Code

Eulerian Trail
(graph/eulerian_trail.hpp)