Eulerian Trail (オイラー路)
(Src/Graph/EulerianTrail.hpp)

• View this file on GitHub
• Last update: 2025-05-27 19:35:07+09:00
• Include: #include "Src/Graph/EulerianTrail.hpp"

概要

オイラー路が存在するなら構築する。オイラー路とは全ての辺を丁度一回ずつ通るようなtrailを指す。

無向グラフ $(V, E)$ において以下の条件を満たすとき、またそのときに限りオイラー路が存在する。

1. 次数 $0$ の頂点を削除したとき、連結である
2. 次数が奇数の頂点が丁度二つ、またはひとつも存在しない

特に条件2で後者を満たすとき、オイラー路の始点と終点が一致する。

有向グラフ $(V, E)$ において以下の条件を満たすとき、またそのときに限りオイラー路が存在する。

1. 次数 $0$ の頂点を削除したとき、連結である

2. 以下のいずれか片方を満たす(両方を同時に満たすことはありえない)

   • 入次数-出次数=1である頂点がちょうど一つ、-1である頂点がちょうど一つ、残りの頂点は0である
   • 全ての頂点について入次数と出次数が等しい

ライブラリの使い方

temlplate <class T>
std::optional<std::pair<std::vector<T>, std::vector<usize>>> EulerianTrail(usize n, const std::vector<std::pair<T, T>>& edges, bool directed)

nは頂点数、edgesは辺の列、directedは有向グラフならtrue、無向グラフならfalseを入れる。

返り値がstd::nulloptのとき、入力に対してオイラー路は存在しない。

firstにはオイラー路の頂点列、secondには辺番号の列が順に入っている。

Depends on

• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

• Test/CF/CF1026-E.test.cpp
• Test/LC/eulerian_trail_directed.test.cpp
• Test/LC/eulerian_trail_undirected.test.cpp

Code

#pragma once

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

#include "../Template/TypeAlias.hpp"

namespace zawa {

// first: 頂点列, second: 辺番号列
template <class T>
std::optional<std::pair<std::vector<T>, std::vector<usize>>> EulerianTrail(usize n, const std::vector<std::pair<T, T>>& edges, bool directed) {
    std::vector<std::vector<std::pair<T, usize>>> g(n);
    for (usize i = 0 ; auto [u, v] : edges) {
        assert(u < n);
        assert(v < n);
        g[u].push_back({v, i});
        if (!directed) g[v].push_back({u, i});
        i++;
    }
    std::vector<bool> used(edges.size());
    std::vector<usize> cur(n), es;
    std::vector<T> vs;
    es.reserve(edges.size());
    vs.reserve(edges.size() + 1);
    auto dfs = [&](auto dfs, const T v) -> void {
        while (cur[v] < g[v].size()) {
            auto [x, i] = g[v][cur[v]++];
            if (!used[i]) {
                used[i] = true;
                dfs(dfs, x);
                es.push_back(i);
                vs.push_back(v);
            }
        }
    };
    usize st = edges.size() ? edges[0].first : 0, go = st;
    if (directed) {
        std::vector<usize> deg(n);
        for (auto [u, v] : edges) {
            deg[u]++;
            deg[v]--;
        }
        const usize p1 = 1, m1 = static_cast<usize>(-1);
        bool fnst = false, fngo = false;
        for (usize i = 0 ; i < n ; i++) {
            if (deg[i] == p1) {
                if (fnst) return std::nullopt;
                fnst = true;
                st = i;
            }
            else if (deg[i] == m1) {
                if (fngo) return std::nullopt;
                fngo = true;
                go = i;
            }
            else if (deg[i]) return std::nullopt;
        }
    }
    else {
        usize cntOdd = 0;
        for (usize i = 0 ; i < n ; i++) if (g[i].size() & 1) {
            if (cntOdd++) go = i;
            else st = i;
        }
        if (cntOdd != 0 and cntOdd != 2) return std::nullopt;
    }
    if (n) {
        dfs(dfs, st);
        std::ranges::reverse(vs);
        vs.push_back(go);
        std::ranges::reverse(es);
    }
    if (edges.size() != es.size()) return std::nullopt;
    return std::make_pair(vs, es);
}

} // namespace zawa

#line 2 "Src/Graph/EulerianTrail.hpp"

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

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 10 "Src/Graph/EulerianTrail.hpp"

namespace zawa {

// first: 頂点列, second: 辺番号列
template <class T>
std::optional<std::pair<std::vector<T>, std::vector<usize>>> EulerianTrail(usize n, const std::vector<std::pair<T, T>>& edges, bool directed) {
    std::vector<std::vector<std::pair<T, usize>>> g(n);
    for (usize i = 0 ; auto [u, v] : edges) {
        assert(u < n);
        assert(v < n);
        g[u].push_back({v, i});
        if (!directed) g[v].push_back({u, i});
        i++;
    }
    std::vector<bool> used(edges.size());
    std::vector<usize> cur(n), es;
    std::vector<T> vs;
    es.reserve(edges.size());
    vs.reserve(edges.size() + 1);
    auto dfs = [&](auto dfs, const T v) -> void {
        while (cur[v] < g[v].size()) {
            auto [x, i] = g[v][cur[v]++];
            if (!used[i]) {
                used[i] = true;
                dfs(dfs, x);
                es.push_back(i);
                vs.push_back(v);
            }
        }
    };
    usize st = edges.size() ? edges[0].first : 0, go = st;
    if (directed) {
        std::vector<usize> deg(n);
        for (auto [u, v] : edges) {
            deg[u]++;
            deg[v]--;
        }
        const usize p1 = 1, m1 = static_cast<usize>(-1);
        bool fnst = false, fngo = false;
        for (usize i = 0 ; i < n ; i++) {
            if (deg[i] == p1) {
                if (fnst) return std::nullopt;
                fnst = true;
                st = i;
            }
            else if (deg[i] == m1) {
                if (fngo) return std::nullopt;
                fngo = true;
                go = i;
            }
            else if (deg[i]) return std::nullopt;
        }
    }
    else {
        usize cntOdd = 0;
        for (usize i = 0 ; i < n ; i++) if (g[i].size() & 1) {
            if (cntOdd++) go = i;
            else st = i;
        }
        if (cntOdd != 0 and cntOdd != 2) return std::nullopt;
    }
    if (n) {
        dfs(dfs, st);
        std::ranges::reverse(vs);
        vs.push_back(go);
        std::ranges::reverse(es);
    }
    if (edges.size() != es.size()) return std::nullopt;
    return std::make_pair(vs, es);
}

} // namespace zawa

Back to top page