C++ Library for Competitive Programming
/*
* @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;
}