cycle.hpp¶
检测有向图或无向图中的一个环，并在无环时给出拓扑序；适合判环及恢复环上顶点/边。
Complexity: Time: O((V + E) log V) for lexicographic topological sort; O(V + E) cycle checks. Space: O(V + E).
AC 记录：cycle_detection, cycle_detection_undirected。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O((V + E) log V) for lexicographic topological sort; O(V +
/// E) cycle checks. Space: O(V + E).
#include "atcoder/dsu.hpp"
#include <algorithm>
#include <cassert>
#include <functional>
#include <optional>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
struct undirected_cycle {
std::vector<int> vs;
std::vector<int> es;
};
/// @brief Return the edge IDs of one directed cycle in traversal order.
inline std::optional<std::vector<int>>
find_directed_cycle(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
std::vector<std::vector<std::pair<int, int>>> G(n);
for (int e = 0; e < int(es.size()); e++) {
auto [u1, to] = es[e];
assert(0 <= u1 && u1 < n);
assert(0 <= to && to < n);
G[u1].emplace_back(to, e);
}
std::vector<unsigned char> st(n);
std::vector<int> fa(n, -1);
std::vector<int> pe(n, -1);
std::vector<int> res;
std::function<bool(int)> dfs = [&](int x) {
st[x] = 1;
for (auto [nxt, e] : G[x]) {
if (st[nxt] == 0) {
fa[nxt] = x;
pe[nxt] = e;
if (dfs(nxt)) {
return true;
}
} else if (st[nxt] == 1) {
for (int cur = x; cur != nxt; cur = fa[cur]) {
res.push_back(pe[cur]);
}
std::reverse(res.begin(), res.end());
res.push_back(e);
return true;
}
}
st[x] = 2;
return false;
};
for (int x = 0; x < n; x++) {
if (st[x] == 0 && dfs(x)) {
return res;
}
}
return std::nullopt;
}
/// @brief Return one simple undirected cycle as aligned vertex and edge IDs.
inline std::optional<undirected_cycle>
find_undirected_cycle(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
std::vector<std::vector<std::pair<int, int>>> G(n);
for (int e = 0; e < int(es.size()); e++) {
auto [a1, b1] = es[e];
assert(0 <= a1 && a1 < n);
assert(0 <= b1 && b1 < n);
G[a1].emplace_back(b1, e);
G[b1].emplace_back(a1, e);
}
std::vector<unsigned char> st(n);
std::vector<int> fa(n, -1);
std::vector<int> pe(n, -1);
undirected_cycle res;
std::function<bool(int, int)> dfs = [&](int x, int ie) {
st[x] = 1;
for (auto [nxt, e] : G[x]) {
if (e == ie) {
continue;
}
if (st[nxt] == 0) {
fa[nxt] = x;
pe[nxt] = e;
if (dfs(nxt, e)) {
return true;
}
} else if (st[nxt] == 1) {
for (int cur = x;; cur = fa[cur]) {
res.vs.push_back(cur);
if (cur == nxt) {
break;
}
res.es.push_back(pe[cur]);
}
std::reverse(res.vs.begin(), res.vs.end());
std::reverse(res.es.begin(), res.es.end());
res.es.push_back(e);
return true;
}
}
st[x] = 2;
return false;
};
for (int x = 0; x < n; x++) {
if (st[x] == 0 && dfs(x, -1)) {
return res;
}
}
return std::nullopt;
}
/// @brief Return the lexicographically smallest topological order, or an empty
/// vector if the directed graph contains a cycle.
inline std::vector<int>
topological_sort(const std::vector<std::vector<int>> &g) {
int N = int(g.size());
std::vector<int> deg(N);
for (const auto &gi : g) {
for (int v : gi) {
deg[v] += 1;
}
}
std::priority_queue<int, std::vector<int>, std::greater<>> que;
for (int i = 0; i < N; i++) {
if (deg[i] == 0) {
que.push(i);
}
}
std::vector<int> ord;
while (!que.empty()) {
int u = que.top();
que.pop();
ord.push_back(u);
for (auto v : g[u]) {
deg[v] -= 1;
if (!deg[v]) {
que.push(v);
}
}
}
if (int(ord.size()) != N) {
return {};
}
return ord;
}
/// @brief Detect whether a directed graph contains a cycle.
inline bool cycle_detection_directed(const std::vector<std::vector<int>> &g) {
return topological_sort(g).size() != g.size();
}
/// @brief Detect whether an undirected edge list contains a cycle.
inline bool
cycle_detection_undirected(const std::vector<std::pair<int, int>> &e) {
int N = 0;
for (auto &[a, b] : e) {
N = std::max(N, a);
N = std::max(N, b);
}
N++;
atcoder::dsu f(N);
for (auto &[a, b] : e) {
if (f.same(a, b)) {
return true;
}
f.merge(a, b);
}
return false;
}
} // namespace noya
#ifndef NOYA_CYCLE_HPP
#define NOYA_CYCLE_HPP 1
/// @complexity Time: O((V + E) log V) for lexicographic topological sort; O(V +
/// E) cycle checks. Space: O(V + E).
#include "atcoder/dsu.hpp"
#include <algorithm>
#include <cassert>
#include <functional>
#include <optional>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
struct undirected_cycle {
std::vector<int> vs;
std::vector<int> es;
};
/// @brief Return the edge IDs of one directed cycle in traversal order.
inline std::optional<std::vector<int>>
find_directed_cycle(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
std::vector<std::vector<std::pair<int, int>>> G(n);
for (int e = 0; e < int(es.size()); e++) {
auto [u1, to] = es[e];
assert(0 <= u1 && u1 < n);
assert(0 <= to && to < n);
G[u1].emplace_back(to, e);
}
std::vector<unsigned char> st(n);
std::vector<int> fa(n, -1);
std::vector<int> pe(n, -1);
std::vector<int> res;
std::function<bool(int)> dfs = [&](int x) {
st[x] = 1;
for (auto [nxt, e] : G[x]) {
if (st[nxt] == 0) {
fa[nxt] = x;
pe[nxt] = e;
if (dfs(nxt)) {
return true;
}
} else if (st[nxt] == 1) {
for (int cur = x; cur != nxt; cur = fa[cur]) {
res.push_back(pe[cur]);
}
std::reverse(res.begin(), res.end());
res.push_back(e);
return true;
}
}
st[x] = 2;
return false;
};
for (int x = 0; x < n; x++) {
if (st[x] == 0 && dfs(x)) {
return res;
}
}
return std::nullopt;
}
/// @brief Return one simple undirected cycle as aligned vertex and edge IDs.
inline std::optional<undirected_cycle>
find_undirected_cycle(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
std::vector<std::vector<std::pair<int, int>>> G(n);
for (int e = 0; e < int(es.size()); e++) {
auto [a1, b1] = es[e];
assert(0 <= a1 && a1 < n);
assert(0 <= b1 && b1 < n);
G[a1].emplace_back(b1, e);
G[b1].emplace_back(a1, e);
}
std::vector<unsigned char> st(n);
std::vector<int> fa(n, -1);
std::vector<int> pe(n, -1);
undirected_cycle res;
std::function<bool(int, int)> dfs = [&](int x, int ie) {
st[x] = 1;
for (auto [nxt, e] : G[x]) {
if (e == ie) {
continue;
}
if (st[nxt] == 0) {
fa[nxt] = x;
pe[nxt] = e;
if (dfs(nxt, e)) {
return true;
}
} else if (st[nxt] == 1) {
for (int cur = x;; cur = fa[cur]) {
res.vs.push_back(cur);
if (cur == nxt) {
break;
}
res.es.push_back(pe[cur]);
}
std::reverse(res.vs.begin(), res.vs.end());
std::reverse(res.es.begin(), res.es.end());
res.es.push_back(e);
return true;
}
}
st[x] = 2;
return false;
};
for (int x = 0; x < n; x++) {
if (st[x] == 0 && dfs(x, -1)) {
return res;
}
}
return std::nullopt;
}
/// @brief Return the lexicographically smallest topological order, or an empty
/// vector if the directed graph contains a cycle.
inline std::vector<int>
topological_sort(const std::vector<std::vector<int>> &g) {
int N = int(g.size());
std::vector<int> deg(N);
for (const auto &gi : g) {
for (int v : gi) {
deg[v] += 1;
}
}
std::priority_queue<int, std::vector<int>, std::greater<>> que;
for (int i = 0; i < N; i++) {
if (deg[i] == 0) {
que.push(i);
}
}
std::vector<int> ord;
while (!que.empty()) {
int u = que.top();
que.pop();
ord.push_back(u);
for (auto v : g[u]) {
deg[v] -= 1;
if (!deg[v]) {
que.push(v);
}
}
}
if (int(ord.size()) != N) {
return {};
}
return ord;
}
/// @brief Detect whether a directed graph contains a cycle.
inline bool cycle_detection_directed(const std::vector<std::vector<int>> &g) {
return topological_sort(g).size() != g.size();
}
/// @brief Detect whether an undirected edge list contains a cycle.
inline bool
cycle_detection_undirected(const std::vector<std::pair<int, int>> &e) {
int N = 0;
for (auto &[a, b] : e) {
N = std::max(N, a);
N = std::max(N, b);
}
N++;
atcoder::dsu f(N);
for (auto &[a, b] : e) {
if (f.same(a, b)) {
return true;
}
f.merge(a, b);
}
return false;
}
} // namespace noya
#endif // NOYA_CYCLE_HPP
#include <algorithm>
#include <cassert>
#include <functional>
#include <optional>
#include <queue>
#include <utility>
#include <vector>
/// @complexity Time: O((V + E) log V) for lexicographic topological sort; O(V +
/// E) cycle checks. Space: O(V + E).
namespace atcoder {
// Implement (union by size) + (path compression)
// Reference:
// Zvi Galil and Giuseppe F. Italiano,
// Data structures and algorithms for disjoint set union problems
struct dsu {
public:
dsu() : _n(0) {}
explicit dsu(int n) : _n(n), parent_or_size(n, -1) {}
int merge(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
int x = leader(a), y = leader(b);
if (x == y) return x;
if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
return x;
}
bool same(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
return leader(a) == leader(b);
}
int leader(int a) {
assert(0 <= a && a < _n);
return _leader(a);
}
int size(int a) {
assert(0 <= a && a < _n);
return -parent_or_size[leader(a)];
}
std::vector<std::vector<int>> groups() {
std::vector<int> leader_buf(_n), group_size(_n);
for (int i = 0; i < _n; i++) {
leader_buf[i] = leader(i);
group_size[leader_buf[i]]++;
}
std::vector<std::vector<int>> result(_n);
for (int i = 0; i < _n; i++) {
result[i].reserve(group_size[i]);
}
for (int i = 0; i < _n; i++) {
result[leader_buf[i]].push_back(i);
}
result.erase(
std::remove_if(result.begin(), result.end(),
[&](const std::vector<int>& v) { return v.empty(); }),
result.end());
return result;
}
private:
int _n;
// root node: -1 * component size
// otherwise: parent
std::vector<int> parent_or_size;
int _leader(int a) {
if (parent_or_size[a] < 0) return a;
return parent_or_size[a] = _leader(parent_or_size[a]);
}
};
} // namespace atcoder
namespace noya {
struct undirected_cycle {
std::vector<int> vs;
std::vector<int> es;
};
/// @brief Return the edge IDs of one directed cycle in traversal order.
inline std::optional<std::vector<int>>
find_directed_cycle(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
std::vector<std::vector<std::pair<int, int>>> G(n);
for (int e = 0; e < int(es.size()); e++) {
auto [u1, to] = es[e];
assert(0 <= u1 && u1 < n);
assert(0 <= to && to < n);
G[u1].emplace_back(to, e);
}
std::vector<unsigned char> st(n);
std::vector<int> fa(n, -1);
std::vector<int> pe(n, -1);
std::vector<int> res;
std::function<bool(int)> dfs = [&](int x) {
st[x] = 1;
for (auto [nxt, e] : G[x]) {
if (st[nxt] == 0) {
fa[nxt] = x;
pe[nxt] = e;
if (dfs(nxt)) {
return true;
}
} else if (st[nxt] == 1) {
for (int cur = x; cur != nxt; cur = fa[cur]) {
res.push_back(pe[cur]);
}
std::reverse(res.begin(), res.end());
res.push_back(e);
return true;
}
}
st[x] = 2;
return false;
};
for (int x = 0; x < n; x++) {
if (st[x] == 0 && dfs(x)) {
return res;
}
}
return std::nullopt;
}
/// @brief Return one simple undirected cycle as aligned vertex and edge IDs.
inline std::optional<undirected_cycle>
find_undirected_cycle(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
std::vector<std::vector<std::pair<int, int>>> G(n);
for (int e = 0; e < int(es.size()); e++) {
auto [a1, b1] = es[e];
assert(0 <= a1 && a1 < n);
assert(0 <= b1 && b1 < n);
G[a1].emplace_back(b1, e);
G[b1].emplace_back(a1, e);
}
std::vector<unsigned char> st(n);
std::vector<int> fa(n, -1);
std::vector<int> pe(n, -1);
undirected_cycle res;
std::function<bool(int, int)> dfs = [&](int x, int ie) {
st[x] = 1;
for (auto [nxt, e] : G[x]) {
if (e == ie) {
continue;
}
if (st[nxt] == 0) {
fa[nxt] = x;
pe[nxt] = e;
if (dfs(nxt, e)) {
return true;
}
} else if (st[nxt] == 1) {
for (int cur = x;; cur = fa[cur]) {
res.vs.push_back(cur);
if (cur == nxt) {
break;
}
res.es.push_back(pe[cur]);
}
std::reverse(res.vs.begin(), res.vs.end());
std::reverse(res.es.begin(), res.es.end());
res.es.push_back(e);
return true;
}
}
st[x] = 2;
return false;
};
for (int x = 0; x < n; x++) {
if (st[x] == 0 && dfs(x, -1)) {
return res;
}
}
return std::nullopt;
}
/// @brief Return the lexicographically smallest topological order, or an empty
/// vector if the directed graph contains a cycle.
inline std::vector<int>
topological_sort(const std::vector<std::vector<int>> &g) {
int N = int(g.size());
std::vector<int> deg(N);
for (const auto &gi : g) {
for (int v : gi) {
deg[v] += 1;
}
}
std::priority_queue<int, std::vector<int>, std::greater<>> que;
for (int i = 0; i < N; i++) {
if (deg[i] == 0) {
que.push(i);
}
}
std::vector<int> ord;
while (!que.empty()) {
int u = que.top();
que.pop();
ord.push_back(u);
for (auto v : g[u]) {
deg[v] -= 1;
if (!deg[v]) {
que.push(v);
}
}
}
if (int(ord.size()) != N) {
return {};
}
return ord;
}
/// @brief Detect whether a directed graph contains a cycle.
inline bool cycle_detection_directed(const std::vector<std::vector<int>> &g) {
return topological_sort(g).size() != g.size();
}
/// @brief Detect whether an undirected edge list contains a cycle.
inline bool
cycle_detection_undirected(const std::vector<std::pair<int, int>> &e) {
int N = 0;
for (auto &[a, b] : e) {
N = std::max(N, a);
N = std::max(N, b);
}
N++;
atcoder::dsu f(N);
for (auto &[a, b] : e) {
if (f.same(a, b)) {
return true;
}
f.merge(a, b);
}
return false;
}
} // namespace noya