C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
#include "emthrm/graph/detect_path.hpp"
$O(\lvert V \rvert + \lvert E \rvert)$
template <typename CostType>
std::vector<Edge<CostType>> detect_path(const std::vector<std::vector<Edge<CostType>>>& graph, const int s, const int t);
std::vector<Edge<CostType>> detect_directed_cycle(const std::vector<std::vector<Edge<CostType>>>& graph);
有向閉路の検出
#ifndef EMTHRM_GRAPH_DETECT_PATH_HPP_ #define EMTHRM_GRAPH_DETECT_PATH_HPP_ #include <vector> #include "emthrm/graph/edge.hpp" namespace emthrm { template <typename CostType> std::vector<Edge<CostType>> detect_path( const std::vector<std::vector<Edge<CostType>>>& graph, const int s, const int t) { std::vector<bool> is_visited(graph.size(), false); std::vector<Edge<CostType>> path; const auto dfs = [&graph, t, &is_visited, &path](auto dfs, const int ver) -> bool { if (ver == t) return true; is_visited[ver] = true; for (const Edge<CostType>& e : graph[ver]) { if (!is_visited[e.dst]) { path.emplace_back(e); if (dfs(dfs, e.dst)) return true; path.pop_back(); } } return false; }; dfs(dfs, s); return path; } } // namespace emthrm #endif // EMTHRM_GRAPH_DETECT_PATH_HPP_
#line 1 "include/emthrm/graph/detect_path.hpp" #include <vector> #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 7 "include/emthrm/graph/detect_path.hpp" namespace emthrm { template <typename CostType> std::vector<Edge<CostType>> detect_path( const std::vector<std::vector<Edge<CostType>>>& graph, const int s, const int t) { std::vector<bool> is_visited(graph.size(), false); std::vector<Edge<CostType>> path; const auto dfs = [&graph, t, &is_visited, &path](auto dfs, const int ver) -> bool { if (ver == t) return true; is_visited[ver] = true; for (const Edge<CostType>& e : graph[ver]) { if (!is_visited[e.dst]) { path.emplace_back(e); if (dfs(dfs, e.dst)) return true; path.pop_back(); } } return false; }; dfs(dfs, s); return path; } } // namespace emthrm