tests/cycle_detection/directed.test.cpp

• View this file on GitHub
• Last update: 2025-01-22 03:51:11+00:00
• Problem: https://judge.yosupo.jp/problem/cycle_detection

Depends on

• Cycle detection on a graph (tools/cycle_detection.hpp)

Code

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

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

using ll = long long;

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

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

  const auto answer = graph.query();
  if (answer) {
    std::cout << answer->second.size() << '\n';
    for (const auto& e : answer->second) {
      std::cout << e << '\n';
    }
  } else {
    std::cout << -1 << '\n';
  }

  return 0;
}

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

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



#include <vector>
#include <cstddef>
#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 5 "tests/cycle_detection/directed.test.cpp"

using ll = long long;

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

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

  const auto answer = graph.query();
  if (answer) {
    std::cout << answer->second.size() << '\n';
    for (const auto& e : answer->second) {
      std::cout << e << '\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	4 ms	4 MB
g++	example_02	AC	4 ms	4 MB
g++	long_cycle_00	AC	181 ms	76 MB
g++	long_cycle_01	AC	195 ms	75 MB
g++	random_00	AC	91 ms	50 MB
g++	random_01	AC	109 ms	57 MB
g++	random_02	AC	69 ms	21 MB
g++	random_03	AC	31 ms	39 MB
g++	random_04	AC	42 ms	30 MB
g++	random_05	AC	85 ms	43 MB
g++	random_06	AC	88 ms	49 MB
g++	random_07	AC	12 ms	11 MB
g++	random_08	AC	67 ms	36 MB
g++	random_09	AC	40 ms	19 MB
g++	random_dag_00	AC	127 ms	51 MB
g++	random_dag_01	AC	142 ms	57 MB
g++	random_dag_02	AC	75 ms	20 MB
g++	random_dag_03	AC	31 ms	39 MB
g++	random_dag_04	AC	41 ms	30 MB
g++	random_dag_05	AC	114 ms	43 MB
g++	random_dag_06	AC	89 ms	49 MB
g++	random_dag_07	AC	12 ms	11 MB
g++	random_dag_08	AC	84 ms	37 MB
g++	random_dag_09	AC	48 ms	18 MB
g++	random_dag_dense_00	AC	53 ms	16 MB
g++	random_dag_dense_01	AC	54 ms	15 MB
g++	random_dag_dense_02	AC	54 ms	17 MB
g++	random_dag_dense_03	AC	56 ms	16 MB
g++	random_dag_dense_04	AC	61 ms	17 MB
g++	random_dense_00	AC	49 ms	18 MB
g++	random_dense_01	AC	50 ms	17 MB
g++	random_dense_02	AC	47 ms	16 MB
g++	random_dense_03	AC	52 ms	20 MB
g++	random_dense_04	AC	55 ms	17 MB

Back to top page