Asa's CP Library

a01sa01to's competitive programming library.

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

View the Project on GitHub a01sa01to/cp-library

:heavy_check_mark: tests/graph/eulerian-walk/libchecker-undirected.test.cpp

Depends on

Code

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using ull = unsigned long long;

#include "../../../cpp/library/graph/eulerian-walk.hpp"
#include "../../../cpp/library/data-structure/graph.hpp"
#define PROBLEM "https://judge.yosupo.jp/problem/eulerian_trail_undirected"

void solve() {
  int n, m;
  cin >> n >> m;
  asalib::graph::graph Graph(n);
  rep(_, m) {
    int u, v;
    cin >> u >> v;
    Graph.add_edge(u, v);
  }
  auto res = Graph.eulerian_walk();
  if (!res.has_value()) {
    cout << "No" << endl;
  }
  else {
    cout << "Yes" << endl;
    auto [vs, es] = res.value();
    rep(i, vs.size()) {
      if (i) cout << " ";
      cout << vs[i];
    }
    cout << endl;
    rep(i, es.size()) {
      if (i) cout << " ";
      cout << es[i];
    }
    cout << endl;
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}
#line 1 "tests/graph/eulerian-walk/libchecker-undirected.test.cpp"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
using ll = long long;
using ull = unsigned long long;

#line 2 "library/graph/eulerian-walk.hpp"

#include <concepts>
#include <optional>
#line 8 "library/graph/eulerian-walk.hpp"
using namespace std;

#line 2 "library/_internal/graph/eulerian-walk.hpp"

#line 8 "library/_internal/graph/eulerian-walk.hpp"
using namespace std;

#line 2 "library/data-structure/graph.hpp"

#line 6 "library/data-structure/graph.hpp"
using namespace std;

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

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

namespace asalib {
  namespace _internal {
    class graph_base {};
    class notweighted_graph_base: public graph_base {};
    class weighted_graph_base: public graph_base {};

    template<typename T>
    concept is_graph = is_base_of_v<graph_base, T>;

    template<typename T>
    concept notweighted_graph = is_base_of_v<notweighted_graph_base, T>;

    template<typename T>
    concept weighted_graph = is_base_of_v<weighted_graph_base, T>;

    using adjlist_t = vector<vector<pair<size_t, size_t>>>;
    using edgelist_t = vector<pair<size_t, size_t>>;
  }  // namespace _internal
}  // namespace asalib
#line 9 "library/data-structure/graph.hpp"

namespace asalib {
  namespace graph {
    class graph: public _internal::notweighted_graph_base {
      public:
      graph(): n_vertex(0), n_edge(0) {}
      explicit graph(size_t n_vertex): n_vertex(n_vertex), n_edge(0) {
        adj_list.reserve(n_vertex);
        adj_list.resize(n_vertex);
      }

      void add_edge(size_t v1, size_t v2) {
        assert(0 <= v1 && v1 < n_vertex);
        assert(0 <= v2 && v2 < n_vertex);
        adj_list[v1].push_back({ v2, n_edge });
        adj_list[v2].push_back({ v1, n_edge });
        edge_list.push_back({ v1, v2 });
        ++n_edge;
      }

      // (v1, v2)
      pair<size_t, size_t> get_edge(size_t edgeId) const {
        assert(0 <= edgeId && edgeId < n_edge);
        return edge_list[edgeId];
      }

      // (v2, edgeId)
      vector<pair<size_t, size_t>> get_adj(size_t vertex) const {
        assert(0 <= vertex && vertex < n_vertex);
        return adj_list[vertex];
      }

      // ---------- prototype ---------- //
      optional<pair<vector<size_t>, vector<size_t>>> cycle() const;
      bool is_connected() const;
      optional<pair<vector<size_t>, vector<size_t>>> eulerian_walk() const;

      private:
      size_t n_vertex, n_edge;
      asalib::_internal::adjlist_t adj_list;
      asalib::_internal::edgelist_t edge_list;
    };
  }  // namespace graph
}  // namespace asalib
#line 11 "library/_internal/graph/eulerian-walk.hpp"

namespace asalib {
  namespace _internal {
    namespace graph {
      template<bool is_directed>
      pair<vector<size_t>, vector<size_t>> eulerian_walk(const size_t& n, const edgelist_t& Edges, const size_t& start_v, const size_t& end_v) {
        // グラフを変換するパート
        vector<queue<size_t>> Graph(n);
        for (size_t i = 0; i < Edges.size(); ++i) {
          const auto& [u, v] = Edges[i];
          Graph[u].push(i);
          if constexpr (!is_directed) Graph[v].push(i);
        }
        vector<bool> used(Edges.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].front();
            Graph[now].pop();
            if (used[e_idx]) continue;
            used[e_idx] = true;
            eds.push_back(e_idx);
            vs.push_back(now);
            const auto& [u, v] = Edges[e_idx];
            if (u == now) {
              now = v;
            }
            else {
              assert(now == v);
              now = u;
            }
          } while (now != to);
          vs.push_back(to);
          return true;
        };

        // 適当に start_v -> end_v のパスを作るパート
        vector<size_t> vs = {}, eds = {};
        find_path(start_v, end_v, vs, eds);
        assert(vs.size() == eds.size() + 1);
        constexpr size_t ign = -1;
        eds.push_back(ign);

        // 別の道があれば寄り道して辺を全部使うパート (閉路になるはず)
        vector<size_t> res_vs, res_eds;
        for (size_t i = 0; i < eds.size(); ++i) {
          stack<size_t> v, e;
          v.push(vs[i]), e.push(eds[i]);
          while (!v.empty()) {
            assert(v.size() == e.size());
            size_t now = v.top();
            size_t e_idx = e.top();
            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();
              reverse(tmpvs.begin(), tmpvs.end());
              reverse(tmpeds.begin(), tmpeds.end());
              for (const auto& ver : tmpvs) v.push(ver);
              for (const auto& edg : tmpeds) e.push(edg);
            }
            else {
              v.pop(), e.pop();
              res_vs.push_back(now);
              res_eds.push_back(e_idx);
            }
          }
        }
        assert(res_eds.back() == ign);
        res_eds.pop_back();
        assert(res_vs.size() == res_eds.size() + 1);
        assert(res_eds.size() == Edges.size());

        return make_pair(res_vs, res_eds);
      }
    }  // namespace graph
  }  // namespace _internal
}  // namespace asalib
#line 2 "library/data-structure/digraph.hpp"

#line 6 "library/data-structure/digraph.hpp"
using namespace std;

#line 10 "library/data-structure/digraph.hpp"

namespace asalib {
  namespace graph {
    class digraph: public _internal::notweighted_graph_base {
      public:
      digraph(): n_vertex(0), n_edge(0) {}
      explicit digraph(size_t n_vertex): n_vertex(n_vertex), n_edge(0) {
        adj_list.reserve(n_vertex);
        adj_list.resize(n_vertex);
        adj_list_rev.reserve(n_vertex);
        adj_list_rev.resize(n_vertex);
        underlying_graph = graph(n_vertex);
      }

      void add_edge(size_t from, size_t to) {
        assert(0 <= from && from < n_vertex);
        assert(0 <= to && to < n_vertex);
        adj_list[from].push_back({ to, n_edge });
        adj_list_rev[to].push_back({ from, n_edge });
        edge_list.push_back({ from, to });
        underlying_graph.add_edge(from, to);
        ++n_edge;
      }

      // (from, to)
      pair<size_t, size_t> get_edge(size_t edgeId) const {
        assert(0 <= edgeId && edgeId < n_edge);
        return edge_list[edgeId];
      }

      // (to, edgeId)
      vector<pair<size_t, size_t>> get_adj(size_t vertex) const {
        assert(0 <= vertex && vertex < n_vertex);
        return adj_list[vertex];
      }

      // (from, edgeId)
      vector<pair<size_t, size_t>> get_adjrev(size_t vertex) const {
        assert(0 <= vertex && vertex < n_vertex);
        return adj_list_rev[vertex];
      }

      // ---------- prototype ---------- //
      vector<vector<size_t>> scc() const;
      optional<pair<vector<size_t>, vector<size_t>>> cycle() const;
      bool is_connected() const;
      optional<pair<vector<size_t>, vector<size_t>>> eulerian_walk() const;

      private:
      size_t n_vertex, n_edge;
      asalib::_internal::adjlist_t adj_list, adj_list_rev;
      asalib::_internal::edgelist_t edge_list;
      graph underlying_graph;
    };
  }  // namespace graph
}  // namespace asalib
#line 2 "library/graph/connection.hpp"

using namespace std;

#line 2 "library/_internal/graph/connection.hpp"

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

#line 8 "library/_internal/graph/connection.hpp"

namespace asalib {
  namespace _internal {
    namespace graph {
      bool is_connected(const adjlist_t& adjlist) {
        vector<bool> visited(adjlist.size(), false);
        function<void(size_t)> dfs = [&](size_t v) {
          visited[v] = true;
          for (const auto& [u, _] : adjlist[v])
            if (!visited[u]) dfs(u);
        };
        dfs(0);
        return all_of(visited.begin(), visited.end(), [](bool v) {
          return v;
        });
      }
    }  // namespace graph
  }  // namespace _internal
}  // namespace asalib
#line 8 "library/graph/connection.hpp"

namespace asalib {
  namespace graph {
    bool digraph::is_connected() const { return _internal::graph::is_connected(adj_list); }
    bool graph::is_connected() const { return _internal::graph::is_connected(adj_list); }
  }  // namespace graph
}  // namespace asalib
#line 14 "library/graph/eulerian-walk.hpp"

namespace asalib {
  namespace graph {
    optional<pair<vector<size_t>, vector<size_t>>> digraph::eulerian_walk() const {
      constexpr size_t None = -1;

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

      // 辺がない頂点を除外したグラフを作る
      size_t n_vertex_withedge = 0;
      vector<size_t> id(n_vertex, None);
      for (const auto& [u, v] : edge_list) {
        if (id[u] == None) id[u] = n_vertex_withedge++;
        if (id[v] == None) id[v] = n_vertex_withedge++;
      }
      vector<size_t> idrev(n_vertex_withedge, None);
      for (size_t i = 0; i < n_vertex; ++i)
        if (id[i] != None) idrev[id[i]] = i;

      asalib::graph::digraph newGraph(n_vertex_withedge);
      for (const auto& [u, v] : edge_list) newGraph.add_edge(id[u], id[v]);

      // 有向グラフの場合、基底無向グラフが連結でなければ存在しない
      if (!newGraph.underlying_graph.is_connected()) return nullopt;

      // オイラーグラフとなるか判定
      vector<size_t> in(n_vertex_withedge, 0), out(n_vertex_withedge, 0);
      for (const auto& [u, v] : edge_list) ++out[id[u]], ++in[id[v]];
      size_t start = None, end = None;
      for (size_t i = 0; i < n_vertex_withedge; ++i) {
        if (in[i] == out[i]) continue;
        if (in[i] + 1 == out[i]) {
          if (start != None) return nullopt;
          start = i;
          continue;
        }
        if (in[i] == out[i] + 1) {
          if (end != None) return nullopt;
          end = i;
          continue;
        }
        return nullopt;
      }
      if ((start == None) xor (end == None)) return nullopt;
      if (start == None) {
        assert(end == None);
        start = end = 0;
      }

      auto [vertexes, edges] = asalib::_internal::graph::eulerian_walk<true>(n_vertex_withedge, newGraph.edge_list, start, end);
      vector<size_t> vertexes_original;
      for (const auto& v : vertexes) vertexes_original.push_back(idrev[v]);

      return make_pair(vertexes_original, edges);
    }

    optional<pair<vector<size_t>, vector<size_t>>> graph::eulerian_walk() const {
      constexpr size_t None = -1;

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

      // 辺のない頂点を除外したグラフを作る
      size_t n_vertex_withedge = 0;
      vector<size_t> id(n_vertex, None);
      for (const auto& [u, v] : edge_list) {
        if (id[u] == None) id[u] = n_vertex_withedge++;
        if (id[v] == None) id[v] = n_vertex_withedge++;
      }
      vector<size_t> idrev(n_vertex_withedge, None);
      for (size_t i = 0; i < n_vertex; ++i)
        if (id[i] != None) idrev[id[i]] = i;

      asalib::graph::graph newGraph(n_vertex_withedge);
      for (const auto& [u, v] : edge_list) newGraph.add_edge(id[u], id[v]);

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

      vector<size_t> deg(n_vertex_withedge, 0);
      for (const auto& [u, v] : edge_list) ++deg[id[u]], ++deg[id[v]];
      size_t start = None, end = None;
      for (size_t i = 0; i < n_vertex_withedge; ++i) {
        if (deg[i] % 2 == 0) continue;
        if (start == None)
          start = i;
        else if (end == None)
          end = i;
        else
          return nullopt;
      }
      if (start != None && end == None) return nullopt;
      if (start == None) {
        assert(end == None);
        start = end = 0;
      }

      auto [vertexes, edges] = asalib::_internal::graph::eulerian_walk<false>(n_vertex_withedge, newGraph.edge_list, start, end);
      vector<size_t> vertexes_original;
      for (const auto& v : vertexes) vertexes_original.push_back(idrev[v]);

      return make_pair(vertexes_original, edges);
    }
  }  // namespace graph
}  // namespace asalib
#line 9 "tests/graph/eulerian-walk/libchecker-undirected.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/eulerian_trail_undirected"

void solve() {
  int n, m;
  cin >> n >> m;
  asalib::graph::graph Graph(n);
  rep(_, m) {
    int u, v;
    cin >> u >> v;
    Graph.add_edge(u, v);
  }
  auto res = Graph.eulerian_walk();
  if (!res.has_value()) {
    cout << "No" << endl;
  }
  else {
    cout << "Yes" << endl;
    auto [vs, es] = res.value();
    rep(i, vs.size()) {
      if (i) cout << " ";
      cout << vs[i];
    }
    cout << endl;
    rep(i, es.size()) {
      if (i) cout << " ";
      cout << es[i];
    }
    cout << endl;
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}
Back to top page