#include "graph/cycle-detection.hpp"
#pragma once #include <utility> #include <vector> using namespace std; #include "./graph-template.hpp" template <typename G> vector<pair<int, int>> CycleDetection(const G& g, bool directed = true) { for (int i = 0; i < (int)g.size(); i++) { for (auto j : g[i]) { if (i == j) { vector<pair<int, int>> res; res.emplace_back(i, i); return res; } } } vector<int> pidx(g.size(), -1), vis(g.size(), 0); vector<pair<int, int>> cycle; int finish = 0; auto dfs = [&](auto rec, int cur, int pval, int par) -> int { pidx[cur] = pval; vis[cur] = 1; for (auto& dst : g[cur]) { if (finish) return -1; if (!directed && dst == par) continue; if (pidx[dst] == pidx[cur]) { cycle.emplace_back(cur, dst); return dst; } if (vis[dst]) continue; int nx = rec(rec, dst, pval, cur); if (nx != -1) { cycle.emplace_back(cur, dst); if (cur == nx) { finish = 1; return -1; } return nx; } } pidx[cur] = -1; return -1; }; for (int i = 0; i < (int)g.size(); i++) { if (vis[i]) continue; dfs(dfs, i, i, -1); if (finish) { reverse(begin(cycle), end(cycle)); return cycle; } } return vector<pair<int, int>>{}; } /** * @brief 閉路の検出 */
#line 2 "graph/cycle-detection.hpp" #include <utility> #include <vector> using namespace std; #line 2 "graph/graph-template.hpp" template <typename T> struct edge { int src, to; T cost; edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {} edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {} edge &operator=(const int &x) { to = x; return *this; } operator int() const { return to; } }; template <typename T> using Edges = vector<edge<T>>; template <typename T> using WeightedGraph = vector<Edges<T>>; using UnweightedGraph = vector<vector<int>>; // Input of (Unweighted) Graph UnweightedGraph graph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) { UnweightedGraph g(N); if (M == -1) M = N - 1; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; if (is_1origin) x--, y--; g[x].push_back(y); if (!is_directed) g[y].push_back(x); } return g; } // Input of Weighted Graph template <typename T> WeightedGraph<T> wgraph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) { WeightedGraph<T> g(N); if (M == -1) M = N - 1; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; cin >> c; if (is_1origin) x--, y--; g[x].emplace_back(x, y, c); if (!is_directed) g[y].emplace_back(y, x, c); } return g; } // Input of Edges template <typename T> Edges<T> esgraph(int N, int M, int is_weighted = true, bool is_1origin = true) { Edges<T> es; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; if (is_weighted) cin >> c; else c = 1; if (is_1origin) x--, y--; es.emplace_back(x, y, c); } return es; } // Input of Adjacency Matrix template <typename T> vector<vector<T>> adjgraph(int N, int M, T INF, int is_weighted = true, bool is_directed = false, bool is_1origin = true) { vector<vector<T>> d(N, vector<T>(N, INF)); for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; if (is_weighted) cin >> c; else c = 1; if (is_1origin) x--, y--; d[x][y] = c; if (!is_directed) d[y][x] = c; } return d; } /** * @brief グラフテンプレート * @docs docs/graph/graph-template.md */ #line 8 "graph/cycle-detection.hpp" template <typename G> vector<pair<int, int>> CycleDetection(const G& g, bool directed = true) { for (int i = 0; i < (int)g.size(); i++) { for (auto j : g[i]) { if (i == j) { vector<pair<int, int>> res; res.emplace_back(i, i); return res; } } } vector<int> pidx(g.size(), -1), vis(g.size(), 0); vector<pair<int, int>> cycle; int finish = 0; auto dfs = [&](auto rec, int cur, int pval, int par) -> int { pidx[cur] = pval; vis[cur] = 1; for (auto& dst : g[cur]) { if (finish) return -1; if (!directed && dst == par) continue; if (pidx[dst] == pidx[cur]) { cycle.emplace_back(cur, dst); return dst; } if (vis[dst]) continue; int nx = rec(rec, dst, pval, cur); if (nx != -1) { cycle.emplace_back(cur, dst); if (cur == nx) { finish = 1; return -1; } return nx; } } pidx[cur] = -1; return -1; }; for (int i = 0; i < (int)g.size(); i++) { if (vis[i]) continue; dfs(dfs, i, i, -1); if (finish) { reverse(begin(cycle), end(cycle)); return cycle; } } return vector<pair<int, int>>{}; } /** * @brief 閉路の検出 */