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)

オイラー路

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

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

$O(n + m)$

詳細

Depends on

Verified with

Code

#pragma once

#include <algorithm>
#include <cassert>
#include <optional>
#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<size_t>, vector<size_t>>> eulerian_walk(const size_t n, const T& edgelist, const bool is_directed) {
    constexpr size_t None = -1;

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

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

    vector Graph(n_vertex_withedge, vector<size_t>());
    for (size_t i = 0; i < edgelist.size(); ++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);
    }

    // 連結でなければ存在しない
    if (is_directed) {
      // 基底無向グラフ
      vector underlyingGraph(n_vertex_withedge, vector<size_t>());
      for (const auto& p : edgelist) {
        const auto &u = get<0>(p), v = get<1>(p);
        underlyingGraph[id[u]].emplace_back(id[v]);
        underlyingGraph[id[v]].emplace_back(id[u]);
      }
      if (!is_connected(underlyingGraph)) return nullopt;
    }
    else {
      vector uGraph(n_vertex_withedge, vector<size_t>());
      for (const auto& p : edgelist) {
        const auto &u = get<0>(p), v = get<1>(p);
        uGraph[id[u]].emplace_back(id[v]);
        uGraph[id[v]].emplace_back(id[u]);
      }
      if (!is_connected(uGraph)) return nullopt;
    }

    // オイラーグラフとなるか判定
    vector<size_t> indeg(n_vertex_withedge, 0), outdeg(n_vertex_withedge, 0);
    for (const auto& p : edgelist) {
      const auto &u = get<0>(p), v = get<1>(p);
      ++outdeg[id[u]], ++indeg[id[v]];
    }
    size_t start = None, end = None;
    for (size_t i = 0; i < n_vertex_withedge; ++i) {
      if (is_directed) {
        if (indeg[i] == outdeg[i]) continue;
        if (indeg[i] + 1 == outdeg[i]) {
          if (start != None) return nullopt;
          start = i;
          continue;
        }
        if (indeg[i] == outdeg[i] + 1) {
          if (end != None) return nullopt;
          end = i;
          continue;
        }
        return nullopt;
      }
      if ((indeg[i] + outdeg[i]) % 2 == 0) continue;
      if (start == None)
        start = i;
      else if (end == None)
        end = i;
      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);
    // 適当にパスを見つけるやつ
    auto find_path = [&](size_t from, size_t to, vector<size_t>& vs, vector<size_t>& eds) {
      size_t now = from;
      if (Graph[now].empty()) return false;
      do {
        assert(!Graph[now].empty());
        size_t e_idx = Graph[now].back();
        Graph[now].pop_back();
        if (used[e_idx]) continue;
        used[e_idx] = true;
        eds.emplace_back(e_idx);
        vs.emplace_back(now);
        const auto& p = edgelist[e_idx];
        if (id[get<0>(p)] == now) {
          now = id[get<1>(p)];
        }
        else {
          assert(now == id[get<1>(p)]);
          now = id[get<0>(p)];
        }
      } while (now != to);
      vs.emplace_back(to);
      return true;
    };
    // start -> end のパスを作るパート
    vector<size_t> vs = {}, eds = {};
    find_path(start, end, vs, eds);
    assert(vs.size() == eds.size() + 1);
    eds.emplace_back(None);
    // 別の道があれば寄り道して辺を全部使うパート (閉路になる)
    vector<size_t> res_vs, res_eds;
    for (size_t i = 0; i < eds.size(); ++i) {
      vector<size_t> v, e;
      v.emplace_back(vs[i]), e.emplace_back(eds[i]);
      while (!v.empty()) {
        assert(v.size() == e.size());
        size_t now = v.back();
        size_t e_idx = e.back();
        vector<size_t> tmpvs, tmpeds;
        if (find_path(now, now, tmpvs, tmpeds)) {
          assert(tmpvs.front() == now && tmpvs.back() == now);
          assert(tmpvs.size() == tmpeds.size() + 1);
          tmpvs.pop_back();
          ranges::reverse(tmpvs);
          ranges::reverse(tmpeds);
          for (const auto& ver : tmpvs) v.emplace_back(ver);
          for (const auto& edg : tmpeds) e.emplace_back(edg);
        }
        else {
          v.pop_back(), e.pop_back();
          res_vs.emplace_back(now);
          res_eds.emplace_back(e_idx);
        }
      }
    }
    assert(res_eds.back() == None);
    res_eds.pop_back();
    assert(res_vs.size() == res_eds.size() + 1);
    assert(res_eds.size() == edgelist.size());

    // 元の頂点番号に戻す
    vector<size_t> vertexes_original;
    for (const auto& v : res_vs) vertexes_original.emplace_back(idrev[v]);

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

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

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

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

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

  // 辺のリストを表す型
  // 重み付きも考慮し pair<int, int> と tuple<int, int, int> の両方を許容
  template<class T>
  concept edge_list = requires(T t) {
    { t.size() } -> convertible_to<size_t>;
    { get<0>(t[0]) } -> convertible_to<size_t>;
    { get<1>(t[0]) } -> convertible_to<size_t>;
  };
}  // 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.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 12 "library/graph/eulerian-walk.hpp"

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

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

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

    vector Graph(n_vertex_withedge, vector<size_t>());
    for (size_t i = 0; i < edgelist.size(); ++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);
    }

    // 連結でなければ存在しない
    if (is_directed) {
      // 基底無向グラフ
      vector underlyingGraph(n_vertex_withedge, vector<size_t>());
      for (const auto& p : edgelist) {
        const auto &u = get<0>(p), v = get<1>(p);
        underlyingGraph[id[u]].emplace_back(id[v]);
        underlyingGraph[id[v]].emplace_back(id[u]);
      }
      if (!is_connected(underlyingGraph)) return nullopt;
    }
    else {
      vector uGraph(n_vertex_withedge, vector<size_t>());
      for (const auto& p : edgelist) {
        const auto &u = get<0>(p), v = get<1>(p);
        uGraph[id[u]].emplace_back(id[v]);
        uGraph[id[v]].emplace_back(id[u]);
      }
      if (!is_connected(uGraph)) return nullopt;
    }

    // オイラーグラフとなるか判定
    vector<size_t> indeg(n_vertex_withedge, 0), outdeg(n_vertex_withedge, 0);
    for (const auto& p : edgelist) {
      const auto &u = get<0>(p), v = get<1>(p);
      ++outdeg[id[u]], ++indeg[id[v]];
    }
    size_t start = None, end = None;
    for (size_t i = 0; i < n_vertex_withedge; ++i) {
      if (is_directed) {
        if (indeg[i] == outdeg[i]) continue;
        if (indeg[i] + 1 == outdeg[i]) {
          if (start != None) return nullopt;
          start = i;
          continue;
        }
        if (indeg[i] == outdeg[i] + 1) {
          if (end != None) return nullopt;
          end = i;
          continue;
        }
        return nullopt;
      }
      if ((indeg[i] + outdeg[i]) % 2 == 0) continue;
      if (start == None)
        start = i;
      else if (end == None)
        end = i;
      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);
    // 適当にパスを見つけるやつ
    auto find_path = [&](size_t from, size_t to, vector<size_t>& vs, vector<size_t>& eds) {
      size_t now = from;
      if (Graph[now].empty()) return false;
      do {
        assert(!Graph[now].empty());
        size_t e_idx = Graph[now].back();
        Graph[now].pop_back();
        if (used[e_idx]) continue;
        used[e_idx] = true;
        eds.emplace_back(e_idx);
        vs.emplace_back(now);
        const auto& p = edgelist[e_idx];
        if (id[get<0>(p)] == now) {
          now = id[get<1>(p)];
        }
        else {
          assert(now == id[get<1>(p)]);
          now = id[get<0>(p)];
        }
      } while (now != to);
      vs.emplace_back(to);
      return true;
    };
    // start -> end のパスを作るパート
    vector<size_t> vs = {}, eds = {};
    find_path(start, end, vs, eds);
    assert(vs.size() == eds.size() + 1);
    eds.emplace_back(None);
    // 別の道があれば寄り道して辺を全部使うパート (閉路になる)
    vector<size_t> res_vs, res_eds;
    for (size_t i = 0; i < eds.size(); ++i) {
      vector<size_t> v, e;
      v.emplace_back(vs[i]), e.emplace_back(eds[i]);
      while (!v.empty()) {
        assert(v.size() == e.size());
        size_t now = v.back();
        size_t e_idx = e.back();
        vector<size_t> tmpvs, tmpeds;
        if (find_path(now, now, tmpvs, tmpeds)) {
          assert(tmpvs.front() == now && tmpvs.back() == now);
          assert(tmpvs.size() == tmpeds.size() + 1);
          tmpvs.pop_back();
          ranges::reverse(tmpvs);
          ranges::reverse(tmpeds);
          for (const auto& ver : tmpvs) v.emplace_back(ver);
          for (const auto& edg : tmpeds) e.emplace_back(edg);
        }
        else {
          v.pop_back(), e.pop_back();
          res_vs.emplace_back(now);
          res_eds.emplace_back(e_idx);
        }
      }
    }
    assert(res_eds.back() == None);
    res_eds.pop_back();
    assert(res_vs.size() == res_eds.size() + 1);
    assert(res_eds.size() == edgelist.size());

    // 元の頂点番号に戻す
    vector<size_t> vertexes_original;
    for (const auto& v : res_vs) vertexes_original.emplace_back(idrev[v]);

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