graph/eulerian_trail.hpp

• View this file on GitHub
• Last update: 2025-09-02 16:51:47+09:00
• Include: #include "graph/eulerian_trail.hpp"

Depends on

• graph/graph.hpp

Verified with

• graph/test/eulerian_trail_directed.test.cpp
• graph/test/eulerian_trail_undirected.test.cpp

Code

#pragma once
#include <algorithm>
#include <utility>
#include "graph.hpp"

template <typename T>
std::pair<std::vector<int>, std::vector<int>> eulerian_trail_directed(
    const Graph<T, true> &g) {
    assert(g.v() >= 1);
    std::vector<int> vs, es;
    std::vector<int> itr(g.v(), 0);
    auto dfs = [&](auto dfs, int v) -> void {
        while (itr[v] < g[v].size()) {
            const Edge<T> &e = g[v][itr[v]++];
            dfs(dfs, e.to);
            vs.push_back(e.to);
            es.push_back(e.id);
        }
    };

    std::vector<int> flux(g.v(), 0);
    for (int i = 0; i < g.v(); ++i) {
        flux[i] += g[i].size();
        for (auto e : g[i]) {
            --flux[e.to];
        }
    }
    int st = -1;
    for (int i = 0; i < g.v(); ++i) {
        if (flux[i] == 1) {
            if (st != -1) {
                // no eulerian trail
                return std::make_pair(vs, es);
            }
            st = i;
        }
        if (flux[i] >= 2) {
            // no eulerian trail
            return std::make_pair(vs, es);
        }
    }
    if (st == -1) {
        for (int i = 0; i < g.v(); ++i) {
            if (g[i].size() > 0) {
                st = i;
            }
        }
    }
    if (st == -1) {
        // no edge
        vs.push_back(0);
        return std::make_pair(vs, es);
    }

    vs.reserve(g.e() + 1);
    es.reserve(g.e());
    dfs(dfs, st);
    if ((int)es.size() != g.e()) {
        return std::make_pair(std::vector<int>(), std::vector<int>());
    }
    vs.push_back(st);
    std::reverse(vs.begin(), vs.end());
    std::reverse(es.begin(), es.end());
    return std::make_pair(vs, es);
}

template <typename T>
std::pair<std::vector<int>, std::vector<int>> eulerian_trail_undirected(
    const Graph<T, false> &g) {
    assert(g.v() >= 1);
    std::vector<int> vs, es;

    int st = -1;
    int cnt = 0;
    for (int i = 0; i < g.v(); ++i) {
        int deg = g[i].size();
        if (deg % 2 == 1) {
            ++cnt;
            st = i;
        }
    }
    if (cnt >= 3) {
        // no eulerian trail
        return std::make_pair(std::vector<int>(), std::vector<int>());
    }
    if (st == -1) {
        for (int i = 0; i < g.v(); ++i) {
            if (g[i].size() > 0) {
                st = i;
            }
        }
    }
    if (st == -1) {
        // no edge
        vs.push_back(0);
        return std::make_pair(vs, es);
    }

    std::vector<int> itr(g.v(), 0), used(g.e(), 0);
    auto dfs = [&](auto dfs, int v) -> void {
        while (itr[v] < g[v].size()) {
            const Edge<T> &e = g[v][itr[v]++];
            if (std::exchange(used[e.id], 1)) {
                continue;
            }
            dfs(dfs, e.to);
            vs.push_back(e.to);
            es.push_back(e.id);
        }
    };

    vs.reserve(g.e() + 1);
    es.reserve(g.e());
    dfs(dfs, st);
    if ((int)es.size() != g.e()) {
        return std::make_pair(std::vector<int>(), std::vector<int>());
    }
    vs.push_back(st);
    std::reverse(vs.begin(), vs.end());
    std::reverse(es.begin(), es.end());
    return std::make_pair(vs, es);
}

// (vs, es)
template <typename T, bool DIR>
std::pair<std::vector<int>, std::vector<int>> eulerian_trail(
    const Graph<T, DIR> &g) {
    if constexpr (DIR) {
        return eulerian_trail_directed(g);
    } else {
        return eulerian_trail_undirected(g);
    }
}

#line 2 "graph/eulerian_trail.hpp"
#include <algorithm>
#include <utility>
#line 2 "graph/graph.hpp"
#include <iostream>
#include <cassert>
#include <vector>
template <typename T>
struct Edge {
    using W = T;
    int from, to, id;
    W weight;
    Edge<T> rev() const {
        return Edge<T>{to, from, id, weight};
    }
};
template <typename T>
void debug(const Edge<T> &e) {
    std::cerr << e.from << " -> " << e.to << " id = " << e.id << std::cerr << " weight = ";
    debug(e.weight);
}
template <typename T = int, bool DIR = false>
class Graph {
public:
    using E = Edge<T>;
    using W = T;
    static constexpr bool DIRECTED = DIR;
    struct Adjacency {
        using Iter = typename std::vector<E>::iterator;
        Iter be, en;
        Iter begin() const { return be; }
        Iter end() const { return en; }
        int size() const { return (int)std::distance(be, en); }
        E &operator[](int idx) const { return be[idx]; }
    };
    struct ConstAdjacency {
        using Iter = typename std::vector<E>::const_iterator;
        Iter be, en;
        Iter begin() const { return be; }
        Iter end() const { return en; }
        int size() const { return (int)std::distance(be, en); }
        const E &operator[](int idx) const { return be[idx]; }
    };

private:
    int n, m;
    std::vector<E> edges, csr;
    std::vector<int> sep;
    bool built;

public:
    Graph(int n) : n(n), m(0), built(false) {}
    int v() const { return n; }
    int e() const { return m; }
    int add_vertex() {
        return n++;
    }
    void add_edge(int from, int to, W weight = 1) {
        assert(0 <= from && from < n && 0 <= to && to < n);
        edges.emplace_back(E{from, to, m++, weight});
    }
    void build() {
        sep.assign(n + 1, 0);
        csr.resize(DIRECTED ? m : 2 * m);
        for (const E &e : edges) {
            ++sep[e.from + 1];
            if (!DIRECTED) {
                ++sep[e.to + 1];
            }
        }
        for (int i = 0; i < n; ++i) {
            sep[i + 1] += sep[i];
        }
        std::vector<int> c = sep;
        for (const E &e : edges) {
            csr[c[e.from]++] = e;
            if (!DIRECTED) {
                csr[c[e.to]++] = e.rev();
            }
        }
        built = true;
    }
    Adjacency operator[](int v) {
        assert(built && 0 <= v && v < n);
        return Adjacency{csr.begin() + sep[v], csr.begin() + sep[v + 1]};
    }
    ConstAdjacency operator[](int v) const {
        assert(built && 0 <= v && v < n);
        return ConstAdjacency{csr.begin() + sep[v], csr.begin() + sep[v + 1]};
    }
};
#line 5 "graph/eulerian_trail.hpp"

template <typename T>
std::pair<std::vector<int>, std::vector<int>> eulerian_trail_directed(
    const Graph<T, true> &g) {
    assert(g.v() >= 1);
    std::vector<int> vs, es;
    std::vector<int> itr(g.v(), 0);
    auto dfs = [&](auto dfs, int v) -> void {
        while (itr[v] < g[v].size()) {
            const Edge<T> &e = g[v][itr[v]++];
            dfs(dfs, e.to);
            vs.push_back(e.to);
            es.push_back(e.id);
        }
    };

    std::vector<int> flux(g.v(), 0);
    for (int i = 0; i < g.v(); ++i) {
        flux[i] += g[i].size();
        for (auto e : g[i]) {
            --flux[e.to];
        }
    }
    int st = -1;
    for (int i = 0; i < g.v(); ++i) {
        if (flux[i] == 1) {
            if (st != -1) {
                // no eulerian trail
                return std::make_pair(vs, es);
            }
            st = i;
        }
        if (flux[i] >= 2) {
            // no eulerian trail
            return std::make_pair(vs, es);
        }
    }
    if (st == -1) {
        for (int i = 0; i < g.v(); ++i) {
            if (g[i].size() > 0) {
                st = i;
            }
        }
    }
    if (st == -1) {
        // no edge
        vs.push_back(0);
        return std::make_pair(vs, es);
    }

    vs.reserve(g.e() + 1);
    es.reserve(g.e());
    dfs(dfs, st);
    if ((int)es.size() != g.e()) {
        return std::make_pair(std::vector<int>(), std::vector<int>());
    }
    vs.push_back(st);
    std::reverse(vs.begin(), vs.end());
    std::reverse(es.begin(), es.end());
    return std::make_pair(vs, es);
}

template <typename T>
std::pair<std::vector<int>, std::vector<int>> eulerian_trail_undirected(
    const Graph<T, false> &g) {
    assert(g.v() >= 1);
    std::vector<int> vs, es;

    int st = -1;
    int cnt = 0;
    for (int i = 0; i < g.v(); ++i) {
        int deg = g[i].size();
        if (deg % 2 == 1) {
            ++cnt;
            st = i;
        }
    }
    if (cnt >= 3) {
        // no eulerian trail
        return std::make_pair(std::vector<int>(), std::vector<int>());
    }
    if (st == -1) {
        for (int i = 0; i < g.v(); ++i) {
            if (g[i].size() > 0) {
                st = i;
            }
        }
    }
    if (st == -1) {
        // no edge
        vs.push_back(0);
        return std::make_pair(vs, es);
    }

    std::vector<int> itr(g.v(), 0), used(g.e(), 0);
    auto dfs = [&](auto dfs, int v) -> void {
        while (itr[v] < g[v].size()) {
            const Edge<T> &e = g[v][itr[v]++];
            if (std::exchange(used[e.id], 1)) {
                continue;
            }
            dfs(dfs, e.to);
            vs.push_back(e.to);
            es.push_back(e.id);
        }
    };

    vs.reserve(g.e() + 1);
    es.reserve(g.e());
    dfs(dfs, st);
    if ((int)es.size() != g.e()) {
        return std::make_pair(std::vector<int>(), std::vector<int>());
    }
    vs.push_back(st);
    std::reverse(vs.begin(), vs.end());
    std::reverse(es.begin(), es.end());
    return std::make_pair(vs, es);
}

// (vs, es)
template <typename T, bool DIR>
std::pair<std::vector<int>, std::vector<int>> eulerian_trail(
    const Graph<T, DIR> &g) {
    if constexpr (DIR) {
        return eulerian_trail_directed(g);
    } else {
        return eulerian_trail_undirected(g);
    }
}

Back to top page