閉路の検出
(graph/cycle-detection.hpp)
Depends on
Verified with
Code
#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([[maybe_unused]] 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 閉路の検出
*/
Back to top page