tests/cycle_detection/undirected.test.cpp

• View this file on GitHub
• Last update: 2025-05-10 19:26:48+09:00
• Problem: https://judge.yosupo.jp/problem/cycle_detection_undirected

Depends on

• Cycle detection on a graph (tools/cycle_detection.hpp)
• Join elements with delimiter (tools/join.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/cycle_detection_undirected

#include <iostream>
#include <cstddef>
#include "tools/cycle_detection.hpp"
#include "tools/join.hpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  std::size_t N, M;
  std::cin >> N >> M;
  tools::cycle_detection<false> graph(N);
  for (std::size_t i = 0; i < M; ++i) {
    std::size_t u, v;
    std::cin >> u >> v;
    graph.add_edge(u, v);
  }

  if (const auto answer = graph.query(); answer) {
    const auto& [vids, eids] = *answer;
    std::cout << vids.size() << '\n';
    std::cout << tools::join(vids, " ") << '\n';
    std::cout << tools::join(eids, " ") << '\n';
  } else {
    std::cout << -1 << '\n';
  }

  return 0;
}

#line 1 "tests/cycle_detection/undirected.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/cycle_detection_undirected

#include <iostream>
#include <cstddef>
#line 1 "tools/cycle_detection.hpp"



#include <vector>
#line 6 "tools/cycle_detection.hpp"
#include <utility>
#include <cassert>
#include <optional>
#include <stack>
#include <tuple>
#include <limits>
#include <algorithm>

namespace tools {
  template <bool DIRECTED>
  class cycle_detection {
  private:
    ::std::vector<::std::vector<::std::size_t>> m_graph;
    ::std::vector<::std::pair<::std::size_t, ::std::size_t>> m_edges;

  public:
    cycle_detection() = default;
    cycle_detection(const ::tools::cycle_detection<DIRECTED>&) = default;
    cycle_detection(::tools::cycle_detection<DIRECTED>&&) = default;
    ~cycle_detection() = default;
    ::tools::cycle_detection<DIRECTED>& operator=(const ::tools::cycle_detection<DIRECTED>&) = default;
    ::tools::cycle_detection<DIRECTED>& operator=(::tools::cycle_detection<DIRECTED>&&) = default;

    explicit cycle_detection(const ::std::size_t n) :
      m_graph(n) {
    }

    ::std::size_t size() const {
      return this->m_graph.size();
    }

    ::std::size_t add_edge(::std::size_t u, ::std::size_t v) {
      assert(u < this->size());
      assert(v < this->size());

      this->m_graph[u].push_back(this->m_edges.size());
      if (!DIRECTED) {
        this->m_graph[v].push_back(this->m_edges.size());
      }
      this->m_edges.emplace_back(u, v);
      return this->m_edges.size() - 1;
    }

    ::std::optional<::std::pair<::std::vector<::std::size_t>, ::std::vector<::std::size_t>>> query() const {
      ::std::stack<std::tuple<bool, ::std::size_t, ::std::size_t>> stack;
      for (::std::size_t v = 0; v < this->size(); ++v) {
        stack.emplace(false, v, ::std::numeric_limits<::std::size_t>::max());
        stack.emplace(true, v, ::std::numeric_limits<::std::size_t>::max());
      }
      ::std::vector<bool> pre(this->size(), false);
      ::std::vector<bool> post(this->size(), false);
      ::std::vector<::std::size_t> prev(this->size(), ::std::numeric_limits<::std::size_t>::max());
      while (!stack.empty()) {
        const auto [is_pre, here, from] = stack.top();
        stack.pop();
        if (post[here]) continue;

        if (is_pre) {
          prev[here] = from;
          if (pre[here]) {
            ::std::vector<::std::size_t> vids, eids({from});
            for (::std::size_t v = this->m_edges[from].first ^ (DIRECTED ? 0 : this->m_edges[from].second ^ here); v != here; v = this->m_edges[prev[v]].first ^ (DIRECTED ? 0 : this->m_edges[prev[v]].second ^ v)) {
              vids.push_back(v);
              eids.push_back(prev[v]);
            }
            vids.push_back(here);
            ::std::reverse(vids.begin(), vids.end());
            ::std::reverse(eids.begin(), eids.end());
            return ::std::make_optional(::std::make_pair(vids, eids));
          }
          pre[here] = true;
          for (const auto eid : this->m_graph[here]) {
            if (eid != from) {
              stack.emplace(false, this->m_edges[eid].second ^ (DIRECTED ? 0 : this->m_edges[eid].first ^ here), eid);
              stack.emplace(true, this->m_edges[eid].second ^ (DIRECTED ? 0 : this->m_edges[eid].first ^ here), eid);
            }
          }
        } else {
          post[here] = true;
        }
      }

      return ::std::nullopt;
    }
  };
}


#line 1 "tools/join.hpp"



#include <ranges>
#include <sstream>

namespace tools {
  template <::std::ranges::range R, typename T>
  ::std::string join(R&& e, const T& d) {
    ::std::ostringstream ss;
    auto it = ::std::ranges::begin(e);
    const auto end = ::std::ranges::end(e);
    if (it != end) {
      ss << *it;
      for (++it; it != end; ++it) {
        ss << d << *it;
      }
    }
    return ss.str();
  }
}


#line 7 "tests/cycle_detection/undirected.test.cpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  std::size_t N, M;
  std::cin >> N >> M;
  tools::cycle_detection<false> graph(N);
  for (std::size_t i = 0; i < M; ++i) {
    std::size_t u, v;
    std::cin >> u >> v;
    graph.add_edge(u, v);
  }

  if (const auto answer = graph.query(); answer) {
    const auto& [vids, eids] = *answer;
    std::cout << vids.size() << '\n';
    std::cout << tools::join(vids, " ") << '\n';
    std::cout << tools::join(eids, " ") << '\n';
  } else {
    std::cout << -1 << '\n';
  }

  return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	5 ms	4 MB
g++	example_01	AC	5 ms	4 MB
g++	example_02	AC	4 ms	4 MB
g++	example_03	AC	5 ms	4 MB
g++	example_04	AC	5 ms	4 MB
g++	long_cycle_00	AC	218 ms	76 MB
g++	long_cycle_01	AC	247 ms	75 MB
g++	long_cycle_02	AC	27 ms	12 MB
g++	random_00	AC	118 ms	57 MB
g++	random_01	AC	127 ms	62 MB
g++	random_02	AC	80 ms	25 MB
g++	random_03	AC	35 ms	39 MB
g++	random_04	AC	49 ms	32 MB
g++	random_05	AC	108 ms	49 MB
g++	random_06	AC	81 ms	53 MB
g++	random_07	AC	14 ms	12 MB
g++	random_08	AC	85 ms	41 MB
g++	random_09	AC	50 ms	22 MB
g++	random_dense_00	AC	50 ms	22 MB
g++	random_dense_01	AC	51 ms	21 MB
g++	random_dense_02	AC	54 ms	27 MB
g++	tree_00	AC	157 ms	57 MB
g++	tree_01	AC	195 ms	66 MB
g++	tree_02	AC	22 ms	10 MB
g++	unicyclic_00	AC	133 ms	57 MB
g++	unicyclic_01	AC	147 ms	66 MB
g++	unicyclic_02	AC	21 ms	10 MB

Back to top page