cycle.hpp¶
判断有向图或无向图是否有环，也能返回环上的点或边；拓扑排序返回字典序最小的合法顶点序列。支持自环和重边。
Complexity: Time: \(O(V + E)\) cycle finding and directed detection; \(O(V + E \alpha (V))\) undirected detection; \(O(E + V \log (V + 1))\) lexicographic topological sort. Space: \(O(V + E)\).
AC 记录：cycle_detection, cycle_detection_undirected。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(V + E) cycle finding and directed detection;
/// O(V + E alpha(V)) undirected detection; O(E + V log(V+1)) lexicographic
/// topological sort. Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <functional>
#include <limits>
#include <optional>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
struct undirected_cycle {
std::vector<int> vs;
std::vector<int> es;
};
namespace cycle_detail {
// Stable CSR retains input order; the path records vertices and entering edges.
template <bool directed>
inline std::optional<undirected_cycle>
find(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
assert(es.size() <= std::size_t(std::numeric_limits<int>::max()));
if (es.empty()) return std::nullopt;
std::vector<std::size_t> start(std::size_t(n) + 1);
for (auto [u, v] : es) {
assert(0 <= u && u < n && 0 <= v && v < n);
++start[u];
if constexpr (!directed) ++start[v];
}
for (int u = 0; u < n; u++) start[u + 1] += start[u];
std::vector<int> adj(start.back());
// Reverse insertion preserves input edge order in every CSR row.
for (int e = int(es.size()); e-- > 0;) {
auto [u, v] = es[e];
adj[--start[u]] = e;
if constexpr (!directed) adj[--start[v]] = e;
}
std::vector<std::pair<int, int>> path;
std::vector<int> pos(n, -1); // -1 unseen, -2 finished, otherwise on the path.
undirected_cycle res;
auto dfs = [&](auto &self, int u, int incoming) -> bool {
pos[u] = int(path.size());
path.emplace_back(u, incoming);
for (auto i = start[u]; i < start[u + 1]; ++i) {
int e = adj[i];
if constexpr (!directed) if (e == incoming) continue;
int v = directed ? es[e].second : es[e].first ^ es[e].second ^ u;
if (pos[v] == -1) {
if (self(self, v, e)) return true;
} else if (pos[v] >= 0) {
if constexpr (!directed)
for (int j = pos[v]; j < int(path.size()); ++j)
res.vs.push_back(path[j].first);
for (int j = pos[v] + 1; j < int(path.size()); ++j)
res.es.push_back(path[j].second);
res.es.push_back(e);
return true;
}
}
path.pop_back();
pos[u] = -2;
return false;
};
for (int u = 0; u < n; ++u)
if (pos[u] == -1 && dfs(dfs, u, -1)) return res;
return std::nullopt;
}
} // namespace cycle_detail
/// @brief Return the edge IDs of one directed cycle in traversal order.
/// Loops and parallel edges are allowed. Search roots by ID and edges in input
/// order; return nullopt if acyclic. Require at most INT_MAX input edges.
inline std::optional<std::vector<int>>
find_directed_cycle(int n, const std::vector<std::pair<int, int>> &es) {
auto res = cycle_detail::find<true>(n, es);
if (!res) return std::nullopt;
return std::move(res->es);
}
/// @brief Return one simple undirected cycle as aligned vertex and edge IDs.
/// A loop is a one-edge cycle; two parallel edges form a two-edge cycle.
/// Preserve the same DFS order as find_directed_cycle, skipping the entering
/// edge ID rather than the parent vertex. Require at most INT_MAX input edges.
inline std::optional<undirected_cycle>
find_undirected_cycle(int n, const std::vector<std::pair<int, int>> &es) {
return cycle_detail::find<false>(n, es);
}
/// @brief Return the lexicographically smallest topological order, or an empty
/// vector if the directed graph contains a cycle. Vertex count and indegrees
/// must fit int; endpoints must be valid. Input is unchanged.
inline std::vector<int>
topological_sort(const std::vector<std::vector<int>> &g) {
assert(g.size() <= std::size_t(std::numeric_limits<int>::max()));
int N = int(g.size());
std::vector<int> deg(N);
for (const auto &gi : g) {
for (int v : gi) {
assert(0 <= v && v < N);
assert(deg[v] < std::numeric_limits<int>::max());
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 Linear-time directed cycle check by FIFO indegree elimination.
/// Same input preconditions as topological_sort; no ordering is requested.
inline bool cycle_detection_directed(const std::vector<std::vector<int>> &g) {
assert(g.size() <= std::size_t(std::numeric_limits<int>::max()));
int n = int(g.size());
std::vector<int> deg(n);
for (const auto &row : g) {
for (int v : row) {
assert(0 <= v && v < n);
assert(deg[v] < std::numeric_limits<int>::max());
++deg[v];
}
}
std::vector<int> q;
q.reserve(n);
for (int u = 0; u < n; u++) if (deg[u] == 0) q.push_back(u);
for (std::size_t head = 0; head < q.size(); head++) {
for (int v : g[q[head]]) if (--deg[v] == 0) q.push_back(v);
}
return q.size() != g.size();
}
/// @brief Detect whether an undirected edge list contains a cycle.
/// Loops and parallel edges count as cycles. IDs must be in [0, INT_MAX);
/// V in the complexity bound is one plus the largest ID (zero for no edges).
inline bool
cycle_detection_undirected(const std::vector<std::pair<int, int>> &es) {
if (es.empty()) return false;
int n = 0;
for (auto [a, b] : es) {
assert(0 <= a && a < std::numeric_limits<int>::max());
assert(0 <= b && b < std::numeric_limits<int>::max());
n = std::max(n, std::max(a, b) + 1);
}
std::vector<int> p(n, -1);
auto leader = [&](int u) {
int r = u;
while (p[r] >= 0) r = p[r];
while (u != r) {
int v = p[u];
p[u] = r;
u = v;
}
return r;
};
for (auto [a, b] : es) {
a = leader(a);
b = leader(b);
if (a == b) return true;
if (p[a] > p[b]) std::swap(a, b);
p[a] += p[b];
p[b] = a;
}
return false;
}
} // namespace noya
// NOYA_CYCLE_HPP
#ifndef NOYA_CYCLE_HPP
#define NOYA_CYCLE_HPP 1
/// @complexity Time: O(V + E) cycle finding and directed detection;
/// O(V + E alpha(V)) undirected detection; O(E + V log(V+1)) lexicographic
/// topological sort. Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <functional>
#include <limits>
#include <optional>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
struct undirected_cycle {
std::vector<int> vs;
std::vector<int> es;
};
namespace cycle_detail {
// Stable CSR retains input order; the path records vertices and entering edges.
template <bool directed>
inline std::optional<undirected_cycle>
find(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
assert(es.size() <= std::size_t(std::numeric_limits<int>::max()));
if (es.empty()) return std::nullopt;
std::vector<std::size_t> start(std::size_t(n) + 1);
for (auto [u, v] : es) {
assert(0 <= u && u < n && 0 <= v && v < n);
++start[u];
if constexpr (!directed) ++start[v];
}
for (int u = 0; u < n; u++) start[u + 1] += start[u];
std::vector<int> adj(start.back());
// Reverse insertion preserves input edge order in every CSR row.
for (int e = int(es.size()); e-- > 0;) {
auto [u, v] = es[e];
adj[--start[u]] = e;
if constexpr (!directed) adj[--start[v]] = e;
}
std::vector<std::pair<int, int>> path;
std::vector<int> pos(n, -1); // -1 unseen, -2 finished, otherwise on the path.
undirected_cycle res;
auto dfs = [&](auto &self, int u, int incoming) -> bool {
pos[u] = int(path.size());
path.emplace_back(u, incoming);
for (auto i = start[u]; i < start[u + 1]; ++i) {
int e = adj[i];
if constexpr (!directed) if (e == incoming) continue;
int v = directed ? es[e].second : es[e].first ^ es[e].second ^ u;
if (pos[v] == -1) {
if (self(self, v, e)) return true;
} else if (pos[v] >= 0) {
if constexpr (!directed)
for (int j = pos[v]; j < int(path.size()); ++j)
res.vs.push_back(path[j].first);
for (int j = pos[v] + 1; j < int(path.size()); ++j)
res.es.push_back(path[j].second);
res.es.push_back(e);
return true;
}
}
path.pop_back();
pos[u] = -2;
return false;
};
for (int u = 0; u < n; ++u)
if (pos[u] == -1 && dfs(dfs, u, -1)) return res;
return std::nullopt;
}
} // namespace cycle_detail
/// @brief Return the edge IDs of one directed cycle in traversal order.
/// Loops and parallel edges are allowed. Search roots by ID and edges in input
/// order; return nullopt if acyclic. Require at most INT_MAX input edges.
inline std::optional<std::vector<int>>
find_directed_cycle(int n, const std::vector<std::pair<int, int>> &es) {
auto res = cycle_detail::find<true>(n, es);
if (!res) return std::nullopt;
return std::move(res->es);
}
/// @brief Return one simple undirected cycle as aligned vertex and edge IDs.
/// A loop is a one-edge cycle; two parallel edges form a two-edge cycle.
/// Preserve the same DFS order as find_directed_cycle, skipping the entering
/// edge ID rather than the parent vertex. Require at most INT_MAX input edges.
inline std::optional<undirected_cycle>
find_undirected_cycle(int n, const std::vector<std::pair<int, int>> &es) {
return cycle_detail::find<false>(n, es);
}
/// @brief Return the lexicographically smallest topological order, or an empty
/// vector if the directed graph contains a cycle. Vertex count and indegrees
/// must fit int; endpoints must be valid. Input is unchanged.
inline std::vector<int>
topological_sort(const std::vector<std::vector<int>> &g) {
assert(g.size() <= std::size_t(std::numeric_limits<int>::max()));
int N = int(g.size());
std::vector<int> deg(N);
for (const auto &gi : g) {
for (int v : gi) {
assert(0 <= v && v < N);
assert(deg[v] < std::numeric_limits<int>::max());
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 Linear-time directed cycle check by FIFO indegree elimination.
/// Same input preconditions as topological_sort; no ordering is requested.
inline bool cycle_detection_directed(const std::vector<std::vector<int>> &g) {
assert(g.size() <= std::size_t(std::numeric_limits<int>::max()));
int n = int(g.size());
std::vector<int> deg(n);
for (const auto &row : g) {
for (int v : row) {
assert(0 <= v && v < n);
assert(deg[v] < std::numeric_limits<int>::max());
++deg[v];
}
}
std::vector<int> q;
q.reserve(n);
for (int u = 0; u < n; u++) if (deg[u] == 0) q.push_back(u);
for (std::size_t head = 0; head < q.size(); head++) {
for (int v : g[q[head]]) if (--deg[v] == 0) q.push_back(v);
}
return q.size() != g.size();
}
/// @brief Detect whether an undirected edge list contains a cycle.
/// Loops and parallel edges count as cycles. IDs must be in [0, INT_MAX);
/// V in the complexity bound is one plus the largest ID (zero for no edges).
inline bool
cycle_detection_undirected(const std::vector<std::pair<int, int>> &es) {
if (es.empty()) return false;
int n = 0;
for (auto [a, b] : es) {
assert(0 <= a && a < std::numeric_limits<int>::max());
assert(0 <= b && b < std::numeric_limits<int>::max());
n = std::max(n, std::max(a, b) + 1);
}
std::vector<int> p(n, -1);
auto leader = [&](int u) {
int r = u;
while (p[r] >= 0) r = p[r];
while (u != r) {
int v = p[u];
p[u] = r;
u = v;
}
return r;
};
for (auto [a, b] : es) {
a = leader(a);
b = leader(b);
if (a == b) return true;
if (p[a] > p[b]) std::swap(a, b);
p[a] += p[b];
p[b] = a;
}
return false;
}
} // namespace noya
#endif // NOYA_CYCLE_HPP
/// @complexity Time: O(V + E) cycle finding and directed detection;
/// O(V + E alpha(V)) undirected detection; O(E + V log(V+1)) lexicographic
/// topological sort. Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <functional>
#include <limits>
#include <optional>
#include <queue>
#include <utility>
#include <vector>
namespace noya {
struct undirected_cycle {
std::vector<int> vs;
std::vector<int> es;
};
namespace cycle_detail {
// Stable CSR retains input order; the path records vertices and entering edges.
template <bool directed>
inline std::optional<undirected_cycle>
find(int n, const std::vector<std::pair<int, int>> &es) {
assert(n >= 0);
assert(es.size() <= std::size_t(std::numeric_limits<int>::max()));
if (es.empty()) return std::nullopt;
std::vector<std::size_t> start(std::size_t(n) + 1);
for (auto [u, v] : es) {
assert(0 <= u && u < n && 0 <= v && v < n);
++start[u];
if constexpr (!directed) ++start[v];
}
for (int u = 0; u < n; u++) start[u + 1] += start[u];
std::vector<int> adj(start.back());
// Reverse insertion preserves input edge order in every CSR row.
for (int e = int(es.size()); e-- > 0;) {
auto [u, v] = es[e];
adj[--start[u]] = e;
if constexpr (!directed) adj[--start[v]] = e;
}
std::vector<std::pair<int, int>> path;
std::vector<int> pos(n, -1); // -1 unseen, -2 finished, otherwise on the path.
undirected_cycle res;
auto dfs = [&](auto &self, int u, int incoming) -> bool {
pos[u] = int(path.size());
path.emplace_back(u, incoming);
for (auto i = start[u]; i < start[u + 1]; ++i) {
int e = adj[i];
if constexpr (!directed) if (e == incoming) continue;
int v = directed ? es[e].second : es[e].first ^ es[e].second ^ u;
if (pos[v] == -1) {
if (self(self, v, e)) return true;
} else if (pos[v] >= 0) {
if constexpr (!directed)
for (int j = pos[v]; j < int(path.size()); ++j)
res.vs.push_back(path[j].first);
for (int j = pos[v] + 1; j < int(path.size()); ++j)
res.es.push_back(path[j].second);
res.es.push_back(e);
return true;
}
}
path.pop_back();
pos[u] = -2;
return false;
};
for (int u = 0; u < n; ++u)
if (pos[u] == -1 && dfs(dfs, u, -1)) return res;
return std::nullopt;
}
} // namespace cycle_detail
/// @brief Return the edge IDs of one directed cycle in traversal order.
/// Loops and parallel edges are allowed. Search roots by ID and edges in input
/// order; return nullopt if acyclic. Require at most INT_MAX input edges.
inline std::optional<std::vector<int>>
find_directed_cycle(int n, const std::vector<std::pair<int, int>> &es) {
auto res = cycle_detail::find<true>(n, es);
if (!res) return std::nullopt;
return std::move(res->es);
}
/// @brief Return one simple undirected cycle as aligned vertex and edge IDs.
/// A loop is a one-edge cycle; two parallel edges form a two-edge cycle.
/// Preserve the same DFS order as find_directed_cycle, skipping the entering
/// edge ID rather than the parent vertex. Require at most INT_MAX input edges.
inline std::optional<undirected_cycle>
find_undirected_cycle(int n, const std::vector<std::pair<int, int>> &es) {
return cycle_detail::find<false>(n, es);
}
/// @brief Return the lexicographically smallest topological order, or an empty
/// vector if the directed graph contains a cycle. Vertex count and indegrees
/// must fit int; endpoints must be valid. Input is unchanged.
inline std::vector<int>
topological_sort(const std::vector<std::vector<int>> &g) {
assert(g.size() <= std::size_t(std::numeric_limits<int>::max()));
int N = int(g.size());
std::vector<int> deg(N);
for (const auto &gi : g) {
for (int v : gi) {
assert(0 <= v && v < N);
assert(deg[v] < std::numeric_limits<int>::max());
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 Linear-time directed cycle check by FIFO indegree elimination.
/// Same input preconditions as topological_sort; no ordering is requested.
inline bool cycle_detection_directed(const std::vector<std::vector<int>> &g) {
assert(g.size() <= std::size_t(std::numeric_limits<int>::max()));
int n = int(g.size());
std::vector<int> deg(n);
for (const auto &row : g) {
for (int v : row) {
assert(0 <= v && v < n);
assert(deg[v] < std::numeric_limits<int>::max());
++deg[v];
}
}
std::vector<int> q;
q.reserve(n);
for (int u = 0; u < n; u++) if (deg[u] == 0) q.push_back(u);
for (std::size_t head = 0; head < q.size(); head++) {
for (int v : g[q[head]]) if (--deg[v] == 0) q.push_back(v);
}
return q.size() != g.size();
}
/// @brief Detect whether an undirected edge list contains a cycle.
/// Loops and parallel edges count as cycles. IDs must be in [0, INT_MAX);
/// V in the complexity bound is one plus the largest ID (zero for no edges).
inline bool
cycle_detection_undirected(const std::vector<std::pair<int, int>> &es) {
if (es.empty()) return false;
int n = 0;
for (auto [a, b] : es) {
assert(0 <= a && a < std::numeric_limits<int>::max());
assert(0 <= b && b < std::numeric_limits<int>::max());
n = std::max(n, std::max(a, b) + 1);
}
std::vector<int> p(n, -1);
auto leader = [&](int u) {
int r = u;
while (p[r] >= 0) r = p[r];
while (u != r) {
int v = p[u];
p[u] = r;
u = v;
}
return r;
};
for (auto [a, b] : es) {
a = leader(a);
b = leader(b);
if (a == b) return true;
if (p[a] > p[b]) std::swap(a, b);
p[a] += p[b];
p[b] = a;
}
return false;
}
} // namespace noya
// NOYA_CYCLE_HPP