グラフ/有向閉路の検出
(test/graph/detect_directed_cycle.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Problem: https://judge.yosupo.jp/problem/cycle_detection

Depends on

• 有向閉路 (directed cycle) の検出 (include/emthrm/graph/detect_directed_cycle.hpp)
• 辺 (include/emthrm/graph/edge.hpp)

Code

/*
 * @title グラフ/有向閉路の検出
 *
 * verification-helper: PROBLEM https://judge.yosupo.jp/problem/cycle_detection
 */

#include <iostream>
#include <ranges>
#include <vector>

#include "emthrm/graph/detect_directed_cycle.hpp"
#include "emthrm/graph/edge.hpp"

int main() {
  int n, m;
  std::cin >> n >> m;
  std::vector<std::vector<emthrm::Edge<int>>> graph(n);
  for (int i = 0; i < m; ++i) {
    int u, v;
    std::cin >> u >> v;
    graph[u].emplace_back(u, v, i);
  }
  // GCC 12 adopted P2415.
  const std::vector<emthrm::Edge<int>> cycle =
      emthrm::detect_directed_cycle(graph);
  const auto ev = cycle | std::views::transform(&emthrm::Edge<int>::cost);
  // const auto ev = emthrm::detect_directed_cycle(graph)
  //               | std::views::transform(&emthrm::Edge<int>::cost);
  const int l = ev.size();
  if (l == 0) {
    std::cout << "-1\n";
  } else {
    std::cout << l << '\n';
    for (const int e : ev) std::cout << e << '\n';
  }
  return 0;
}

#line 1 "test/graph/detect_directed_cycle.test.cpp"
/*
 * @title グラフ/有向閉路の検出
 *
 * verification-helper: PROBLEM https://judge.yosupo.jp/problem/cycle_detection
 */

#include <iostream>
#include <ranges>
#include <vector>

#line 1 "include/emthrm/graph/detect_directed_cycle.hpp"



#include <algorithm>
#line 6 "include/emthrm/graph/detect_directed_cycle.hpp"

#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 8 "include/emthrm/graph/detect_directed_cycle.hpp"

namespace emthrm {

template <typename CostType>
std::vector<Edge<CostType>> detect_directed_cycle(
    const std::vector<std::vector<Edge<CostType>>>& graph) {
  const int n = graph.size();
  std::vector<int> is_visited(n, 0);
  std::vector<Edge<CostType>> edges, cycle;
  const auto dfs = [&graph, &is_visited, &edges, &cycle](
      auto dfs, const int ver) -> bool {
    is_visited[ver] = 1;
    for (const Edge<CostType>& e : graph[ver]) {
      if (is_visited[e.dst] == 1) {
        cycle.emplace_back(e);
        while (cycle.back().src != e.dst) {
          cycle.emplace_back(edges.back());
          edges.pop_back();
        }
        std::reverse(cycle.begin(), cycle.end());
        return true;
      } else if (is_visited[e.dst] == 0) {
        edges.emplace_back(e);
        if (dfs(dfs, e.dst)) return true;
        edges.pop_back();
      }
    }
    is_visited[ver] = 2;
    return false;
  };
  for (int i = 0; i < n; ++i) {
    if (is_visited[i] == 0 && dfs(dfs, i)) break;
  }
  return cycle;
}

}  // namespace emthrm


#line 1 "include/emthrm/graph/edge.hpp"
/**
 * @title 辺
 */

#ifndef EMTHRM_GRAPH_EDGE_HPP_
#define EMTHRM_GRAPH_EDGE_HPP_

#include <compare>

namespace emthrm {

template <typename CostType>
struct Edge {
  CostType cost;
  int src, dst;

  explicit Edge(const int src, const int dst, const CostType cost = 0)
      : cost(cost), src(src), dst(dst) {}

  auto operator<=>(const Edge& x) const = default;
};

}  // namespace emthrm

#endif  // EMTHRM_GRAPH_EDGE_HPP_
#line 13 "test/graph/detect_directed_cycle.test.cpp"

int main() {
  int n, m;
  std::cin >> n >> m;
  std::vector<std::vector<emthrm::Edge<int>>> graph(n);
  for (int i = 0; i < m; ++i) {
    int u, v;
    std::cin >> u >> v;
    graph[u].emplace_back(u, v, i);
  }
  // GCC 12 adopted P2415.
  const std::vector<emthrm::Edge<int>> cycle =
      emthrm::detect_directed_cycle(graph);
  const auto ev = cycle | std::views::transform(&emthrm::Edge<int>::cost);
  // const auto ev = emthrm::detect_directed_cycle(graph)
  //               | std::views::transform(&emthrm::Edge<int>::cost);
  const int l = ev.size();
  if (l == 0) {
    std::cout << "-1\n";
  } else {
    std::cout << l << '\n';
    for (const int e : ev) std::cout << e << '\n';
  }
  return 0;
}

Back to top page