cycle.hpp¶
Topological ordering and cycle detection for directed and undirected graphs.
Verified by cycle_detection, cycle_detection_undirected.
检测有向图或无向图中的一个环，并在无环时给出拓扑序；适合判环及恢复环上顶点/边。
Implementation¶
#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> vertices;
std::vector<int> edges;
};
/// @brief Return the edge IDs of one directed cycle in traversal order.
inline std::optional<std::vector<int>>
find_directed_cycle(int vertex_count,
const std::vector<std::pair<int, int>> &edges) {
assert(vertex_count >= 0);
std::vector<std::vector<std::pair<int, int>>> graph(vertex_count);
for (int edge = 0; edge < int(edges.size()); edge++) {
auto [from, to] = edges[edge];
assert(0 <= from && from < vertex_count);
assert(0 <= to && to < vertex_count);
graph[from].emplace_back(to, edge);
}
std::vector<unsigned char> state(vertex_count);
std::vector<int> parent(vertex_count, -1);
std::vector<int> parent_edge(vertex_count, -1);
std::vector<int> result;
std::function<bool(int)> dfs = [&](int vertex) {
state[vertex] = 1;
for (auto [next, edge] : graph[vertex]) {
if (state[next] == 0) {
parent[next] = vertex;
parent_edge[next] = edge;
if (dfs(next)) {
return true;
}
} else if (state[next] == 1) {
for (int current = vertex; current != next; current = parent[current]) {
result.push_back(parent_edge[current]);
}
std::reverse(result.begin(), result.end());
result.push_back(edge);
return true;
}
}
state[vertex] = 2;
return false;
};
for (int vertex = 0; vertex < vertex_count; vertex++) {
if (state[vertex] == 0 && dfs(vertex)) {
return result;
}
}
return std::nullopt;
}
/// @brief Return one simple undirected cycle as aligned vertex and edge IDs.
inline std::optional<undirected_cycle>
find_undirected_cycle(int vertex_count,
const std::vector<std::pair<int, int>> &edges) {
assert(vertex_count >= 0);
std::vector<std::vector<std::pair<int, int>>> graph(vertex_count);
for (int edge = 0; edge < int(edges.size()); edge++) {
auto [first, second] = edges[edge];
assert(0 <= first && first < vertex_count);
assert(0 <= second && second < vertex_count);
graph[first].emplace_back(second, edge);
graph[second].emplace_back(first, edge);
}
std::vector<unsigned char> state(vertex_count);
std::vector<int> parent(vertex_count, -1);
std::vector<int> parent_edge(vertex_count, -1);
undirected_cycle result;
std::function<bool(int, int)> dfs = [&](int vertex, int incoming_edge) {
state[vertex] = 1;
for (auto [next, edge] : graph[vertex]) {
if (edge == incoming_edge) {
continue;
}
if (state[next] == 0) {
parent[next] = vertex;
parent_edge[next] = edge;
if (dfs(next, edge)) {
return true;
}
} else if (state[next] == 1) {
for (int current = vertex;; current = parent[current]) {
result.vertices.push_back(current);
if (current == next) {
break;
}
result.edges.push_back(parent_edge[current]);
}
std::reverse(result.vertices.begin(), result.vertices.end());
std::reverse(result.edges.begin(), result.edges.end());
result.edges.push_back(edge);
return true;
}
}
state[vertex] = 2;
return false;
};
for (int vertex = 0; vertex < vertex_count; vertex++) {
if (state[vertex] == 0 && dfs(vertex, -1)) {
return result;
}
}
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> order;
while (!que.empty()) {
int u = que.top();
que.pop();
order.push_back(u);
for (auto v : g[u]) {
deg[v] -= 1;
if (!deg[v]) {
que.push(v);
}
}
}
if (int(order.size()) != N) {
return {};
}
return order;
}
/// @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>> &edge) {
int N = 0;
for (auto &[a, b] : edge) {
N = std::max(N, a);
N = std::max(N, b);
}
N++;
atcoder::dsu f(N);
for (auto &[a, b] : edge) {
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> vertices;
std::vector<int> edges;
};
/// @brief Return the edge IDs of one directed cycle in traversal order.
inline std::optional<std::vector<int>>
find_directed_cycle(int vertex_count,
const std::vector<std::pair<int, int>> &edges) {
assert(vertex_count >= 0);
std::vector<std::vector<std::pair<int, int>>> graph(vertex_count);
for (int edge = 0; edge < int(edges.size()); edge++) {
auto [from, to] = edges[edge];
assert(0 <= from && from < vertex_count);
assert(0 <= to && to < vertex_count);
graph[from].emplace_back(to, edge);
}
std::vector<unsigned char> state(vertex_count);
std::vector<int> parent(vertex_count, -1);
std::vector<int> parent_edge(vertex_count, -1);
std::vector<int> result;
std::function<bool(int)> dfs = [&](int vertex) {
state[vertex] = 1;
for (auto [next, edge] : graph[vertex]) {
if (state[next] == 0) {
parent[next] = vertex;
parent_edge[next] = edge;
if (dfs(next)) {
return true;
}
} else if (state[next] == 1) {
for (int current = vertex; current != next; current = parent[current]) {
result.push_back(parent_edge[current]);
}
std::reverse(result.begin(), result.end());
result.push_back(edge);
return true;
}
}
state[vertex] = 2;
return false;
};
for (int vertex = 0; vertex < vertex_count; vertex++) {
if (state[vertex] == 0 && dfs(vertex)) {
return result;
}
}
return std::nullopt;
}
/// @brief Return one simple undirected cycle as aligned vertex and edge IDs.
inline std::optional<undirected_cycle>
find_undirected_cycle(int vertex_count,
const std::vector<std::pair<int, int>> &edges) {
assert(vertex_count >= 0);
std::vector<std::vector<std::pair<int, int>>> graph(vertex_count);
for (int edge = 0; edge < int(edges.size()); edge++) {
auto [first, second] = edges[edge];
assert(0 <= first && first < vertex_count);
assert(0 <= second && second < vertex_count);
graph[first].emplace_back(second, edge);
graph[second].emplace_back(first, edge);
}
std::vector<unsigned char> state(vertex_count);
std::vector<int> parent(vertex_count, -1);
std::vector<int> parent_edge(vertex_count, -1);
undirected_cycle result;
std::function<bool(int, int)> dfs = [&](int vertex, int incoming_edge) {
state[vertex] = 1;
for (auto [next, edge] : graph[vertex]) {
if (edge == incoming_edge) {
continue;
}
if (state[next] == 0) {
parent[next] = vertex;
parent_edge[next] = edge;
if (dfs(next, edge)) {
return true;
}
} else if (state[next] == 1) {
for (int current = vertex;; current = parent[current]) {
result.vertices.push_back(current);
if (current == next) {
break;
}
result.edges.push_back(parent_edge[current]);
}
std::reverse(result.vertices.begin(), result.vertices.end());
std::reverse(result.edges.begin(), result.edges.end());
result.edges.push_back(edge);
return true;
}
}
state[vertex] = 2;
return false;
};
for (int vertex = 0; vertex < vertex_count; vertex++) {
if (state[vertex] == 0 && dfs(vertex, -1)) {
return result;
}
}
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> order;
while (!que.empty()) {
int u = que.top();
que.pop();
order.push_back(u);
for (auto v : g[u]) {
deg[v] -= 1;
if (!deg[v]) {
que.push(v);
}
}
}
if (int(order.size()) != N) {
return {};
}
return order;
}
/// @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>> &edge) {
int N = 0;
for (auto &[a, b] : edge) {
N = std::max(N, a);
N = std::max(N, b);
}
N++;
atcoder::dsu f(N);
for (auto &[a, b] : edge) {
if (f.same(a, b)) {
return true;
}
f.merge(a, b);
}
return false;
}
} // namespace noya