Asa's CP Library

a01sa01to's competitive programming library. Requires C++20 or higher with GCC. This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub a01sa01to/cp-library

:heavy_check_mark: オイラー路
(library/graph/eulerian-walk.hpp)

オイラー路

辺のリストを与えられたとき、グラフにオイラー路 (辺を全部ちょうど一回通る路) が存在するかを判定する。

もし存在するなら、{ 頂点の index のリスト, 辺の index のリスト } を返す。 存在しない場合は nullopt を返す。

$O(n + m)$

詳細

Depends on

Verified with

Code

#pragma once

#include <algorithm>
#include <cassert>
#include <optional>
#include <ranges>
#include <utility>
#include <vector>
using namespace std;

#include "../_internal/graph-base.hpp"
#include "./connection.hpp"

namespace asalib::graph {
  template<_internal::edge_list T>
  optional<pair<vector<int>, vector<int>>> eulerian_walk(const int n, const T& edgelist, const bool is_directed) {
    constexpr int None = -1;

    // もし辺がなければオイラーグラフ、任意の頂点を返す
    if (edgelist.empty()) [[unlikely]]
      return make_pair(vector<int> { 0 }, vector<int> {});

    // 辺がない頂点を除外したグラフを作成
    int n_vertex_withedge = 0;
    vector<int> id(n, None), indeg(n, 0), outdeg(n, 0);
    for (const auto& p : edgelist) {
      const auto &u = get<0>(p), &v = get<1>(p);
      ++outdeg[u], ++indeg[v];
      if (id[u] == None) id[u] = n_vertex_withedge++;
      if (id[v] == None) id[v] = n_vertex_withedge++;
    }
    vector idrev(n_vertex_withedge, None);
    for (int i = 0; i < n; ++i)
      if (id[i] != None) idrev[id[i]] = i;

    vector Graph(n_vertex_withedge, vector<int>());
    vector underlyingGraph(n_vertex_withedge, vector<int>());
    for (int i = 0; i < n_vertex_withedge; ++i) {
      const int bidir_siz = indeg[idrev[i]] + outdeg[idrev[i]];
      Graph[i].reserve(is_directed ? outdeg[idrev[i]] : bidir_siz);
      underlyingGraph[i].reserve(bidir_siz);
    }
    for (int i = 0; i < ranges::ssize(edgelist); ++i) {
      const auto& p = edgelist[i];
      const auto &u = get<0>(p), &v = get<1>(p);
      Graph[id[u]].emplace_back(i);
      if (!is_directed) Graph[id[v]].emplace_back(i);
      underlyingGraph[id[u]].emplace_back(id[v]);
      underlyingGraph[id[v]].emplace_back(id[u]);
    }

    // 連結でなければ存在しない
    if (!is_connected(underlyingGraph)) return nullopt;

    // オイラーグラフとなるか判定
    int start = None, end = None;
    for (int idx = 0; idx < n_vertex_withedge; ++idx) {
      const int i = idrev[idx];
      if (is_directed) {
        if (indeg[i] == outdeg[i]) continue;
        if (indeg[i] + 1 == outdeg[i]) {
          if (start != None) return nullopt;
          start = idx;
          continue;
        }
        if (indeg[i] == outdeg[i] + 1) {
          if (end != None) return nullopt;
          end = idx;
          continue;
        }
        return nullopt;
      }
      if ((indeg[i] + outdeg[i]) % 2 == 0) continue;
      if (start == None)
        start = idx;
      else if (end == None)
        end = idx;
      else
        return nullopt;
    }
    if ((start == None) xor (end == None)) return nullopt;

    if (start == None) {
      assert(end == None);
      start = end = 0;
    }

    // グラフ探索パート
    vector<bool> used(edgelist.size(), false);
    vector<int> vs, es;
    vector<pair<int, int>> st = { { start, None } };
    vs.reserve(edgelist.size() + 1);
    es.reserve(edgelist.size());
    st.reserve(edgelist.size() + 1);
    while (!st.empty()) {
      auto [v, inedge] = st.back();
      while (!Graph[v].empty() && used[Graph[v].back()]) Graph[v].pop_back();
      if (Graph[v].empty()) {
        st.pop_back();
        vs.emplace_back(v);
        if (inedge != None) es.emplace_back(inedge);
      }
      else {
        const int e = Graph[v].back();
        Graph[v].pop_back();
        used[e] = true;
        const auto& p = edgelist[e];
        const auto &u = get<0>(p), &w = get<1>(p);
        const int to = id[u] == v ? id[w] : id[u];
        st.emplace_back(to, e);
      }
    }

    assert(vs.size() == es.size() + 1);
    assert(es.size() == edgelist.size());

    ranges::reverse(vs);
    ranges::reverse(es);

    // 元の頂点番号に戻す
    vector<int> vs_orig(vs.size());
    for (int i = 0; i < ranges::ssize(vs); ++i) vs_orig[i] = idrev[vs[i]];

    return make_pair(vs_orig, es);
  }
}  // namespace asalib::graph
#line 2 "library/graph/eulerian-walk.hpp"

#include <algorithm>
#include <cassert>
#include <optional>
#include <ranges>
#include <utility>
#include <vector>
using namespace std;

#line 2 "library/_internal/graph-base.hpp"

#include <concepts>
#line 6 "library/_internal/graph-base.hpp"
using namespace std;

namespace asalib::_internal {
  // vector<vector<int>> とかの隣接リストを表す型
  template<class T>
  concept adjacency_list = requires(T t) {
    ranges::ssize(t);
    { t[0] } -> ranges::range;
    { *ranges::begin(t[0]) } -> convertible_to<int>;
  };

  // 辺のリストを表す型
  // 重み付きも考慮し pair<int, int> と tuple<int, int, int> の両方を許容
  template<class T>
  concept edge_list = requires(T t) {
    ranges::ssize(t);
    { get<0>(t[0]) } -> convertible_to<int>;
    { get<1>(t[0]) } -> convertible_to<int>;
  };
}  // namespace asalib::_internal
#line 2 "library/graph/connection.hpp"

#line 4 "library/graph/connection.hpp"
using namespace std;

#line 7 "library/graph/connection.hpp"

namespace asalib::graph {
  template<_internal::adjacency_list T>
  bool is_connected(const T& adj_list) {
    vector<bool> visited(adj_list.size(), false);
    vector<int> st;
    st.reserve(adj_list.size());
    st.emplace_back(0);
    visited[0] = true;
    while (!st.empty()) {
      int v = st.back();
      st.pop_back();
      for (const auto& u : adj_list[v]) {
        if (!visited[u]) {
          visited[u] = true;
          st.emplace_back(u);
        }
      }
    }
    for (const auto v : visited) {
      if (!v) return false;
    }
    return true;
  }
}  // namespace asalib::graph
#line 13 "library/graph/eulerian-walk.hpp"

namespace asalib::graph {
  template<_internal::edge_list T>
  optional<pair<vector<int>, vector<int>>> eulerian_walk(const int n, const T& edgelist, const bool is_directed) {
    constexpr int None = -1;

    // もし辺がなければオイラーグラフ、任意の頂点を返す
    if (edgelist.empty()) [[unlikely]]
      return make_pair(vector<int> { 0 }, vector<int> {});

    // 辺がない頂点を除外したグラフを作成
    int n_vertex_withedge = 0;
    vector<int> id(n, None), indeg(n, 0), outdeg(n, 0);
    for (const auto& p : edgelist) {
      const auto &u = get<0>(p), &v = get<1>(p);
      ++outdeg[u], ++indeg[v];
      if (id[u] == None) id[u] = n_vertex_withedge++;
      if (id[v] == None) id[v] = n_vertex_withedge++;
    }
    vector idrev(n_vertex_withedge, None);
    for (int i = 0; i < n; ++i)
      if (id[i] != None) idrev[id[i]] = i;

    vector Graph(n_vertex_withedge, vector<int>());
    vector underlyingGraph(n_vertex_withedge, vector<int>());
    for (int i = 0; i < n_vertex_withedge; ++i) {
      const int bidir_siz = indeg[idrev[i]] + outdeg[idrev[i]];
      Graph[i].reserve(is_directed ? outdeg[idrev[i]] : bidir_siz);
      underlyingGraph[i].reserve(bidir_siz);
    }
    for (int i = 0; i < ranges::ssize(edgelist); ++i) {
      const auto& p = edgelist[i];
      const auto &u = get<0>(p), &v = get<1>(p);
      Graph[id[u]].emplace_back(i);
      if (!is_directed) Graph[id[v]].emplace_back(i);
      underlyingGraph[id[u]].emplace_back(id[v]);
      underlyingGraph[id[v]].emplace_back(id[u]);
    }

    // 連結でなければ存在しない
    if (!is_connected(underlyingGraph)) return nullopt;

    // オイラーグラフとなるか判定
    int start = None, end = None;
    for (int idx = 0; idx < n_vertex_withedge; ++idx) {
      const int i = idrev[idx];
      if (is_directed) {
        if (indeg[i] == outdeg[i]) continue;
        if (indeg[i] + 1 == outdeg[i]) {
          if (start != None) return nullopt;
          start = idx;
          continue;
        }
        if (indeg[i] == outdeg[i] + 1) {
          if (end != None) return nullopt;
          end = idx;
          continue;
        }
        return nullopt;
      }
      if ((indeg[i] + outdeg[i]) % 2 == 0) continue;
      if (start == None)
        start = idx;
      else if (end == None)
        end = idx;
      else
        return nullopt;
    }
    if ((start == None) xor (end == None)) return nullopt;

    if (start == None) {
      assert(end == None);
      start = end = 0;
    }

    // グラフ探索パート
    vector<bool> used(edgelist.size(), false);
    vector<int> vs, es;
    vector<pair<int, int>> st = { { start, None } };
    vs.reserve(edgelist.size() + 1);
    es.reserve(edgelist.size());
    st.reserve(edgelist.size() + 1);
    while (!st.empty()) {
      auto [v, inedge] = st.back();
      while (!Graph[v].empty() && used[Graph[v].back()]) Graph[v].pop_back();
      if (Graph[v].empty()) {
        st.pop_back();
        vs.emplace_back(v);
        if (inedge != None) es.emplace_back(inedge);
      }
      else {
        const int e = Graph[v].back();
        Graph[v].pop_back();
        used[e] = true;
        const auto& p = edgelist[e];
        const auto &u = get<0>(p), &w = get<1>(p);
        const int to = id[u] == v ? id[w] : id[u];
        st.emplace_back(to, e);
      }
    }

    assert(vs.size() == es.size() + 1);
    assert(es.size() == edgelist.size());

    ranges::reverse(vs);
    ranges::reverse(es);

    // 元の頂点番号に戻す
    vector<int> vs_orig(vs.size());
    for (int i = 0; i < ranges::ssize(vs); ++i) vs_orig[i] = idrev[vs[i]];

    return make_pair(vs_orig, es);
  }
}  // namespace asalib::graph
Back to top page