DAG Algorithms
(graph/dag.hpp)
- View this file on GitHub
- Last update: 2026-08-24 00:41:13+09:00
- Include:
#include "graph/dag.hpp"
Overview
graph/dag.hpp is the contest-oriented include bundle for directed acyclic
graphs. It combines ordering, weighted paths, path counting, reachability,
transitive reduction, and minimum path cover without introducing a second graph
container.
All algorithms use Graph<T> and ignore inactive edges. Operations that require
acyclic input return std::nullopt when a directed cycle exists.
Included Headers
| Header | Contents |
|---|---|
graph/topological_sort.hpp |
Topological ordering and DAG recognition. |
graph/dag_shortest_path.hpp |
Minimum-cost paths, including negative edge costs. |
graph/dag_longest_path.hpp |
Maximum-cost paths and reconstruction. |
graph/dag_path_count.hpp |
Counts paths from one or more sources. |
graph/dag_reachability.hpp |
Batched reachability and transitive reduction. |
graph/dag_path_cover.hpp |
Minimum vertex-disjoint path cover. |
This header provides no additional runtime operation. See the individual pages for exact signatures, assumptions, and complexities.
Example
#include "graph/dag.hpp"
#include "graph/graph.hpp"
#include <iostream>
int main() {
m1une::graph::Graph<int> g(3);
g.add_directed_edge(0, 1, 4);
g.add_directed_edge(1, 2, 5);
auto longest = m1une::graph::dag_longest_path(g, 0);
auto ways = m1une::graph::dag_path_count(g, 0);
if (longest && ways) {
std::cout << longest->dist[2] << ' ' << (*ways)[2] << '\n';
}
}
Depends on
- Bipartite Graph
(graph/bipartite.hpp)
- DAG Longest Path
(graph/dag_longest_path.hpp)
- DAG Path Count
(graph/dag_path_count.hpp)
- Minimum DAG Path Cover
(graph/dag_path_cover.hpp)
- DAG Reachability and Transitive Reduction
(graph/dag_reachability.hpp)
- DAG Shortest Path
(graph/dag_shortest_path.hpp)
- Graph
(graph/graph.hpp)
- Topological Sort
(graph/topological_sort.hpp)
- Dynamic Bitset
(utilities/dynamic_bitset.hpp)
Required by
Verified with
- verify/graph/cow_game.test.cpp
- verify/graph/dag_algorithms.test.cpp
- verify/graph/graph_algorithms.test.cpp
- verify/graph/range_edge_graph.test.cpp
Code
#ifndef M1UNE_GRAPH_DAG_HPP
#define M1UNE_GRAPH_DAG_HPP 1
#include "dag_longest_path.hpp"
#include "dag_path_count.hpp"
#include "dag_path_cover.hpp"
#include "dag_reachability.hpp"
#include "dag_shortest_path.hpp"
#include "topological_sort.hpp"
#endif // M1UNE_GRAPH_DAG_HPP#line 1 "graph/dag.hpp"
#line 1 "graph/dag_longest_path.hpp"
#include <algorithm>
#include <cassert>
#include <limits>
#include <optional>
#include <vector>
#line 1 "graph/graph.hpp"
#include <array>
#line 6 "graph/graph.hpp"
#include <utility>
#line 8 "graph/graph.hpp"
namespace m1une {
namespace graph {
template <class T = int>
struct Edge {
using cost_type = T;
int from;
int to;
T cost;
int id;
bool alive;
Edge() : from(-1), to(-1), cost(T()), id(-1), alive(true) {}
Edge(int from_, int to_, T cost_ = T(1), int id_ = -1, bool alive_ = true)
: from(from_), to(to_), cost(cost_), id(id_), alive(alive_) {}
int other(int v) const {
assert(v == from || v == to);
return from ^ to ^ v;
}
};
template <class T = int>
struct Graph {
using edge_type = Edge<T>;
using cost_type = T;
private:
struct EdgePositions {
std::array<std::pair<int, int>, 2> value{};
int size = 0;
void push_back(std::pair<int, int> position) {
assert(size < 2);
value[size++] = position;
}
};
int _n;
int _edge_count;
std::vector<std::vector<edge_type>> _g;
std::vector<EdgePositions> _edge_positions;
public:
Graph() : _n(0), _edge_count(0) {}
explicit Graph(int n) : _n(n), _edge_count(0), _g(n) {
assert(0 <= n);
}
int size() const {
return _n;
}
bool empty() const {
return _n == 0;
}
int edge_count() const {
return _edge_count;
}
int add_vertex() {
_g.emplace_back();
return _n++;
}
int add_directed_edge(int from, int to, T cost = T(1)) {
assert(0 <= from && from < _n);
assert(0 <= to && to < _n);
int id = _edge_count++;
int idx = int(_g[from].size());
_g[from].push_back(edge_type(from, to, cost, id));
_edge_positions.emplace_back();
_edge_positions.back().push_back({from, idx});
return id;
}
int add_edge(int u, int v, T cost = T(1)) {
assert(0 <= u && u < _n);
assert(0 <= v && v < _n);
int id = _edge_count++;
int u_idx = int(_g[u].size());
_g[u].push_back(edge_type(u, v, cost, id));
int v_idx = int(_g[v].size());
_g[v].push_back(edge_type(v, u, cost, id));
_edge_positions.emplace_back();
_edge_positions.back().push_back({u, u_idx});
_edge_positions.back().push_back({v, v_idx});
return id;
}
void set_edge_alive(int id, bool alive) {
assert(0 <= id && id < _edge_count);
for (int i = 0; i < _edge_positions[id].size; ++i) {
auto [v, idx] = _edge_positions[id].value[i];
_g[v][idx].alive = alive;
}
}
void erase_edge(int id) {
set_edge_alive(id, false);
}
void revive_edge(int id) {
set_edge_alive(id, true);
}
bool is_edge_alive(int id) const {
assert(0 <= id && id < _edge_count);
assert(_edge_positions[id].size != 0);
auto [v, idx] = _edge_positions[id].value[0];
return _g[v][idx].alive;
}
const std::vector<edge_type>& operator[](int v) const {
assert(0 <= v && v < _n);
return _g[v];
}
std::vector<edge_type>& operator[](int v) {
assert(0 <= v && v < _n);
return _g[v];
}
const std::vector<std::vector<edge_type>>& adjacency() const {
return _g;
}
std::vector<std::vector<edge_type>>& adjacency() {
return _g;
}
std::vector<edge_type> edges(bool include_inactive = false) const {
std::vector<edge_type> result;
result.reserve(_edge_count);
std::vector<char> used(_edge_count, false);
for (int v = 0; v < _n; v++) {
for (const auto& e : _g[v]) {
if (!include_inactive && !e.alive) continue;
if (0 <= e.id && e.id < _edge_count) {
if (used[e.id]) continue;
used[e.id] = true;
}
result.push_back(e);
}
}
return result;
}
Graph reversed() const {
Graph result(_n);
result._edge_count = _edge_count;
result._edge_positions.assign(_edge_count, {});
for (int v = 0; v < _n; v++) {
for (const auto& e : _g[v]) {
int idx = int(result._g[e.to].size());
result._g[e.to].push_back(edge_type(e.to, e.from, e.cost, e.id, e.alive));
if (0 <= e.id && e.id < _edge_count) result._edge_positions[e.id].push_back({e.to, idx});
}
}
return result;
}
};
} // namespace graph
} // namespace m1une
#line 1 "graph/topological_sort.hpp"
#line 5 "graph/topological_sort.hpp"
#include <queue>
#line 7 "graph/topological_sort.hpp"
#line 9 "graph/topological_sort.hpp"
namespace m1une {
namespace graph {
template <class T>
std::optional<std::vector<int>> topological_sort(const Graph<T>& g) {
int n = g.size();
std::vector<int> indeg(n, 0);
for (int v = 0; v < n; v++) {
for (const auto& e : g[v]) {
if (!e.alive) continue;
indeg[e.to]++;
}
}
std::queue<int> que;
for (int v = 0; v < n; v++) {
if (indeg[v] == 0) que.push(v);
}
std::vector<int> order;
order.reserve(n);
while (!que.empty()) {
int v = que.front();
que.pop();
order.push_back(v);
for (const auto& e : g[v]) {
if (!e.alive) continue;
indeg[e.to]--;
if (indeg[e.to] == 0) que.push(e.to);
}
}
if (int(order.size()) != n) return std::nullopt;
return order;
}
template <class T>
bool is_dag(const Graph<T>& g) {
return topological_sort(g).has_value();
}
} // namespace graph
} // namespace m1une
#line 12 "graph/dag_longest_path.hpp"
namespace m1une {
namespace graph {
template <class T>
struct DagLongestPathResult {
std::vector<T> dist;
std::vector<int> parent;
std::vector<int> parent_edge;
std::vector<int> topological_order;
T neg_inf;
bool reachable(int v) const {
assert(0 <= v && v < int(dist.size()));
return dist[v] != neg_inf;
}
std::vector<int> path(int t) const {
assert(reachable(t));
std::vector<int> result;
for (int v = t; v != -1; v = parent[v]) result.push_back(v);
std::reverse(result.begin(), result.end());
return result;
}
};
template <class T>
std::optional<DagLongestPathResult<T>> dag_longest_path(
const Graph<T>& g,
const std::vector<int>& sources,
T neg_inf = std::numeric_limits<T>::lowest() / T(4)
) {
const int n = g.size();
auto order = topological_sort(g);
if (!order) return std::nullopt;
DagLongestPathResult<T> result;
result.dist.assign(n, neg_inf);
result.parent.assign(n, -1);
result.parent_edge.assign(n, -1);
result.topological_order = *order;
result.neg_inf = neg_inf;
for (int s : sources) {
assert(0 <= s && s < n);
result.dist[s] = T(0);
}
for (int v : *order) {
if (result.dist[v] == neg_inf) continue;
for (const auto& e : g[v]) {
if (!e.alive) continue;
T nd = result.dist[v] + e.cost;
if (result.dist[e.to] >= nd) continue;
result.dist[e.to] = nd;
result.parent[e.to] = v;
result.parent_edge[e.to] = e.id;
}
}
return result;
}
template <class T>
std::optional<DagLongestPathResult<T>> dag_longest_path(
const Graph<T>& g,
int s,
T neg_inf = std::numeric_limits<T>::lowest() / T(4)
) {
return dag_longest_path(g, std::vector<int>{s}, neg_inf);
}
} // namespace graph
} // namespace m1une
#line 1 "graph/dag_path_count.hpp"
#line 7 "graph/dag_path_count.hpp"
#line 10 "graph/dag_path_count.hpp"
namespace m1une {
namespace graph {
template <class Count = long long, class T>
std::optional<std::vector<Count>> dag_path_count(
const Graph<T>& g,
const std::vector<int>& sources
) {
const int n = g.size();
auto order = topological_sort(g);
if (!order) return std::nullopt;
std::vector<Count> ways(n, Count(0));
std::vector<char> used_source(n, false);
for (int s : sources) {
assert(0 <= s && s < n);
if (used_source[s]) continue;
used_source[s] = true;
ways[s] += Count(1);
}
for (int v : *order) {
for (const auto& e : g[v]) {
if (e.alive) ways[e.to] += ways[v];
}
}
return ways;
}
template <class Count = long long, class T>
std::optional<std::vector<Count>> dag_path_count(const Graph<T>& g, int s) {
return dag_path_count<Count>(g, std::vector<int>{s});
}
} // namespace graph
} // namespace m1une
#line 1 "graph/dag_path_cover.hpp"
#line 7 "graph/dag_path_cover.hpp"
#line 1 "graph/bipartite.hpp"
#line 6 "graph/bipartite.hpp"
#include <cstddef>
#include <cstdint>
#line 13 "graph/bipartite.hpp"
#line 15 "graph/bipartite.hpp"
namespace m1une {
namespace graph {
struct BipartiteResult {
bool is_bipartite;
std::vector<int> color;
std::vector<int> left_vertices;
std::vector<int> right_vertices;
std::vector<int> left_id;
std::vector<int> right_id;
};
template <class T>
BipartiteResult bipartite(const Graph<T>& g) {
int n = g.size();
BipartiteResult result;
result.is_bipartite = true;
result.color.assign(n, -1);
result.left_id.assign(n, -1);
result.right_id.assign(n, -1);
std::vector<std::vector<int>> adjacency(n);
for (const auto& e : g.edges()) {
adjacency[e.from].push_back(e.to);
adjacency[e.to].push_back(e.from);
}
std::queue<int> que;
for (int s = 0; s < n; s++) {
if (result.color[s] != -1) continue;
result.color[s] = 0;
que.push(s);
while (!que.empty()) {
int v = que.front();
que.pop();
for (int to : adjacency[v]) {
if (result.color[to] == -1) {
result.color[to] = result.color[v] ^ 1;
que.push(to);
} else if (result.color[to] == result.color[v]) {
result.is_bipartite = false;
return result;
}
}
}
}
for (int v = 0; v < n; v++) {
if (result.color[v] == 0) {
result.left_id[v] = int(result.left_vertices.size());
result.left_vertices.push_back(v);
} else {
result.right_id[v] = int(result.right_vertices.size());
result.right_vertices.push_back(v);
}
}
return result;
}
template <class T>
bool is_bipartite(const Graph<T>& g) {
return bipartite(g).is_bipartite;
}
struct BipartiteVertexSet {
std::vector<int> left;
std::vector<int> right;
int size() const {
return int(left.size() + right.size());
}
};
struct BipartiteMatching {
struct Edge {
int left;
int right;
int id;
bool alive;
};
struct Pair {
int left;
int right;
int edge_id;
};
private:
int _left_size;
int _right_size;
std::vector<Edge> _edges;
std::vector<std::vector<int>> _adj;
std::vector<std::vector<int>> _radj;
std::vector<int> _left_match;
std::vector<int> _right_match;
std::vector<int> _left_match_edge;
std::vector<int> _right_match_edge;
bool _calculated;
void invalidate() {
_calculated = false;
}
void ensure_matching() {
if (!_calculated) max_matching();
}
public:
BipartiteMatching() : BipartiteMatching(0, 0) {}
BipartiteMatching(int left_size, int right_size)
: _left_size(left_size),
_right_size(right_size),
_adj(left_size),
_radj(right_size),
_left_match(left_size, -1),
_right_match(right_size, -1),
_left_match_edge(left_size, -1),
_right_match_edge(right_size, -1),
_calculated(false) {
assert(0 <= left_size);
assert(0 <= right_size);
}
int left_size() const {
return _left_size;
}
int right_size() const {
return _right_size;
}
int edge_count() const {
return int(_edges.size());
}
int add_edge(int left, int right) {
assert(0 <= left && left < _left_size);
assert(0 <= right && right < _right_size);
int id = int(_edges.size());
_edges.push_back(Edge{left, right, id, true});
_adj[left].push_back(id);
_radj[right].push_back(id);
invalidate();
return id;
}
Edge get_edge(int i) const {
assert(0 <= i && i < int(_edges.size()));
return _edges[i];
}
std::vector<Edge> edges(bool include_inactive = false) const {
std::vector<Edge> result;
result.reserve(_edges.size());
for (const auto& e : _edges) {
if (include_inactive || e.alive) result.push_back(e);
}
return result;
}
void set_edge_alive(int id, bool alive) {
assert(0 <= id && id < int(_edges.size()));
_edges[id].alive = alive;
invalidate();
}
void erase_edge(int id) {
set_edge_alive(id, false);
}
void revive_edge(int id) {
set_edge_alive(id, true);
}
bool is_edge_alive(int id) const {
assert(0 <= id && id < int(_edges.size()));
return _edges[id].alive;
}
int max_matching() {
_left_match.assign(_left_size, -1);
_right_match.assign(_right_size, -1);
_left_match_edge.assign(_left_size, -1);
_right_match_edge.assign(_right_size, -1);
std::vector<int> dist(_left_size);
auto bfs = [&]() -> bool {
std::queue<int> que;
bool found = false;
for (int l = 0; l < _left_size; l++) {
if (_left_match[l] == -1) {
dist[l] = 0;
que.push(l);
} else {
dist[l] = -1;
}
}
while (!que.empty()) {
int l = que.front();
que.pop();
for (int id : _adj[l]) {
const auto& e = _edges[id];
if (!e.alive) continue;
int next_left = _right_match[e.right];
if (next_left == -1) {
found = true;
} else if (dist[next_left] == -1) {
dist[next_left] = dist[l] + 1;
que.push(next_left);
}
}
}
return found;
};
auto dfs = [&](auto self, int l) -> bool {
for (int id : _adj[l]) {
const auto& e = _edges[id];
if (!e.alive) continue;
int next_left = _right_match[e.right];
if (next_left != -1 && (dist[next_left] != dist[l] + 1 || !self(self, next_left))) {
continue;
}
_left_match[l] = e.right;
_right_match[e.right] = l;
_left_match_edge[l] = id;
_right_match_edge[e.right] = id;
return true;
}
dist[l] = -1;
return false;
};
int result = 0;
while (bfs()) {
for (int l = 0; l < _left_size; l++) {
if (_left_match[l] == -1 && dfs(dfs, l)) result++;
}
}
_calculated = true;
return result;
}
int matching_size() {
ensure_matching();
int result = 0;
for (int right : _left_match) {
if (right != -1) result++;
}
return result;
}
std::vector<int> left_match() {
ensure_matching();
return _left_match;
}
std::vector<int> right_match() {
ensure_matching();
return _right_match;
}
std::vector<Pair> matching() {
ensure_matching();
std::vector<Pair> result;
for (int l = 0; l < _left_size; l++) {
if (_left_match[l] != -1) result.push_back(Pair{l, _left_match[l], _left_match_edge[l]});
}
return result;
}
BipartiteVertexSet minimum_vertex_cover() {
ensure_matching();
std::vector<char> visited_left(_left_size, false), visited_right(_right_size, false);
std::queue<int> que;
for (int l = 0; l < _left_size; l++) {
if (_left_match[l] == -1) {
visited_left[l] = true;
que.push(l);
}
}
while (!que.empty()) {
int l = que.front();
que.pop();
for (int id : _adj[l]) {
const auto& e = _edges[id];
if (!e.alive || _left_match_edge[l] == id || visited_right[e.right]) continue;
visited_right[e.right] = true;
int next_left = _right_match[e.right];
if (next_left != -1 && !visited_left[next_left]) {
visited_left[next_left] = true;
que.push(next_left);
}
}
}
BipartiteVertexSet result;
for (int l = 0; l < _left_size; l++) {
if (!visited_left[l]) result.left.push_back(l);
}
for (int r = 0; r < _right_size; r++) {
if (visited_right[r]) result.right.push_back(r);
}
return result;
}
BipartiteVertexSet maximum_independent_set() {
auto cover = minimum_vertex_cover();
std::vector<char> in_left_cover(_left_size, false), in_right_cover(_right_size, false);
for (int l : cover.left) in_left_cover[l] = true;
for (int r : cover.right) in_right_cover[r] = true;
BipartiteVertexSet result;
for (int l = 0; l < _left_size; l++) {
if (!in_left_cover[l]) result.left.push_back(l);
}
for (int r = 0; r < _right_size; r++) {
if (!in_right_cover[r]) result.right.push_back(r);
}
return result;
}
std::optional<std::vector<int>> minimum_edge_cover() {
ensure_matching();
std::vector<int> result;
std::vector<char> covered_left(_left_size, false), covered_right(_right_size, false);
std::vector<char> used_edge(_edges.size(), false);
auto use_edge = [&](int id) {
if (used_edge[id]) return;
used_edge[id] = true;
result.push_back(id);
covered_left[_edges[id].left] = true;
covered_right[_edges[id].right] = true;
};
for (int l = 0; l < _left_size; l++) {
if (_left_match_edge[l] != -1) use_edge(_left_match_edge[l]);
}
for (int l = 0; l < _left_size; l++) {
if (covered_left[l]) continue;
int id = -1;
for (int edge_id : _adj[l]) {
if (_edges[edge_id].alive) {
id = edge_id;
break;
}
}
if (id == -1) return std::nullopt;
use_edge(id);
}
for (int r = 0; r < _right_size; r++) {
if (covered_right[r]) continue;
int id = -1;
for (int edge_id : _radj[r]) {
if (_edges[edge_id].alive) {
id = edge_id;
break;
}
}
if (id == -1) return std::nullopt;
use_edge(id);
}
return result;
}
};
struct BipartiteMatchingGraph {
BipartiteResult parts;
BipartiteMatching matching;
std::vector<int> original_edge_id;
int left_vertex(int left) const {
assert(0 <= left && left < int(parts.left_vertices.size()));
return parts.left_vertices[left];
}
int right_vertex(int right) const {
assert(0 <= right && right < int(parts.right_vertices.size()));
return parts.right_vertices[right];
}
int original_edge(int edge_id) const {
assert(0 <= edge_id && edge_id < int(original_edge_id.size()));
return original_edge_id[edge_id];
}
};
template <class T>
std::optional<BipartiteMatchingGraph> make_bipartite_matching(const Graph<T>& g) {
auto parts = bipartite(g);
if (!parts.is_bipartite) return std::nullopt;
BipartiteMatchingGraph result;
result.parts = parts;
result.matching = BipartiteMatching(int(parts.left_vertices.size()), int(parts.right_vertices.size()));
for (const auto& e : g.edges()) {
int left, right;
if (parts.color[e.from] == 0) {
left = parts.left_id[e.from];
right = parts.right_id[e.to];
} else {
left = parts.left_id[e.to];
right = parts.right_id[e.from];
}
int id = result.matching.add_edge(left, right);
if (int(result.original_edge_id.size()) <= id) result.original_edge_id.resize(id + 1);
result.original_edge_id[id] = e.id;
}
return result;
}
struct BipartiteEdgeColoringResult {
int color_count;
std::vector<int> color;
};
namespace detail {
struct BipartiteEdgeColoringGroups {
int count;
std::vector<int> group;
};
inline BipartiteEdgeColoringGroups group_vertices(
const std::vector<int>& degree,
int maximum_degree
) {
BipartiteEdgeColoringGroups result;
result.count = 0;
result.group.assign(degree.size(), -1);
int current_degree = 0;
for (int vertex = 0; vertex < int(degree.size()); vertex++) {
if (degree[vertex] == 0) continue;
if (result.count == 0 || current_degree + degree[vertex] > maximum_degree) {
result.count++;
current_degree = 0;
}
result.group[vertex] = result.count - 1;
current_degree += degree[vertex];
}
return result;
}
class BipartiteEdgeColoringSolver {
private:
int _side_size;
int _original_edge_count;
std::vector<int> _left;
std::vector<int> _right;
std::vector<int> _color;
std::vector<int> _used_stamp;
int _stamp;
int other_endpoint(int vertex, int edge) const {
if (vertex < _side_size) return _side_size + _right[edge];
return _left[edge];
}
std::vector<int> perfect_matching(const std::vector<int>& edge_ids) const {
std::vector<std::vector<int>> adjacency(_side_size);
for (int edge : edge_ids) adjacency[_left[edge]].push_back(edge);
std::vector<int> right_match(_side_size, -1);
std::vector<int> left_match_edge(_side_size, -1);
int matching_size = 0;
for (int left = 0; left < _side_size; left++) {
for (int edge : adjacency[left]) {
int right = _right[edge];
if (right_match[right] != -1) continue;
right_match[right] = left;
left_match_edge[left] = edge;
matching_size++;
break;
}
}
std::vector<int> distance(_side_size);
std::vector<int> next_edge(_side_size);
std::vector<int> left_stack;
std::vector<int> path_edges;
left_stack.reserve(_side_size);
path_edges.reserve(_side_size);
while (matching_size < _side_size) {
std::queue<int> queue;
std::fill(distance.begin(), distance.end(), -1);
for (int left = 0; left < _side_size; left++) {
if (left_match_edge[left] != -1) continue;
distance[left] = 0;
queue.push(left);
}
bool reachable_free_right = false;
while (!queue.empty()) {
int left = queue.front();
queue.pop();
for (int edge : adjacency[left]) {
int next_left = right_match[_right[edge]];
if (next_left == -1) {
reachable_free_right = true;
} else if (distance[next_left] == -1) {
distance[next_left] = distance[left] + 1;
queue.push(next_left);
}
}
}
assert(reachable_free_right);
std::fill(next_edge.begin(), next_edge.end(), 0);
int augmented = 0;
for (int root = 0; root < _side_size; root++) {
if (left_match_edge[root] != -1 || distance[root] == -1) continue;
left_stack.clear();
path_edges.clear();
left_stack.push_back(root);
bool found = false;
while (!left_stack.empty() && !found) {
int left = left_stack.back();
bool advanced = false;
while (next_edge[left] < int(adjacency[left].size())) {
int edge = adjacency[left][next_edge[left]++];
int right = _right[edge];
int next_left = right_match[right];
if (next_left == -1) {
left_match_edge[left] = edge;
right_match[right] = left;
for (int index = int(path_edges.size()) - 1; index >= 0; index--) {
int path_edge = path_edges[index];
int path_left = left_stack[index];
left_match_edge[path_left] = path_edge;
right_match[_right[path_edge]] = path_left;
}
found = true;
break;
}
if (distance[next_left] != distance[left] + 1) continue;
path_edges.push_back(edge);
left_stack.push_back(next_left);
advanced = true;
break;
}
if (found || advanced) continue;
distance[left] = -1;
left_stack.pop_back();
if (path_edges.size() == left_stack.size() && !path_edges.empty()) {
path_edges.pop_back();
}
}
if (found) augmented++;
}
assert(augmented > 0);
matching_size += augmented;
}
return left_match_edge;
}
std::pair<std::vector<int>, std::vector<int>> split_even(
const std::vector<int>& edge_ids
) {
std::vector<std::vector<int>> incidence(std::size_t(2) * _side_size);
for (int edge : edge_ids) {
incidence[_left[edge]].push_back(edge);
incidence[_side_size + _right[edge]].push_back(edge);
}
_stamp++;
assert(_stamp > 0);
std::vector<int> next_edge(std::size_t(2) * _side_size, 0);
std::vector<int> first;
std::vector<int> second;
first.reserve(edge_ids.size() / 2);
second.reserve(edge_ids.size() / 2);
for (int start = 0; start < 2 * _side_size; start++) {
while (true) {
while (next_edge[start] < int(incidence[start].size()) &&
_used_stamp[incidence[start][next_edge[start]]] == _stamp) {
next_edge[start]++;
}
if (next_edge[start] == int(incidence[start].size())) break;
int vertex = start;
bool parity = false;
do {
while (next_edge[vertex] < int(incidence[vertex].size()) &&
_used_stamp[incidence[vertex][next_edge[vertex]]] == _stamp) {
next_edge[vertex]++;
}
assert(next_edge[vertex] < int(incidence[vertex].size()));
int edge = incidence[vertex][next_edge[vertex]++];
_used_stamp[edge] = _stamp;
if (!parity) {
first.push_back(edge);
} else {
second.push_back(edge);
}
parity = !parity;
vertex = other_endpoint(vertex, edge);
} while (vertex != start);
assert(!parity);
}
}
assert(first.size() == second.size());
return {std::move(first), std::move(second)};
}
void color_regular(const std::vector<int>& edge_ids, int degree, int offset) {
assert(std::size_t(_side_size) * std::size_t(degree) == edge_ids.size());
if (degree == 0) return;
if (degree == 1) {
for (int edge : edge_ids) {
if (edge < _original_edge_count) _color[edge] = offset;
}
return;
}
if (degree % 2 == 1) {
std::vector<int> matching = perfect_matching(edge_ids);
_stamp++;
assert(_stamp > 0);
for (int edge : matching) {
_used_stamp[edge] = _stamp;
if (edge < _original_edge_count) _color[edge] = offset;
}
std::vector<int> remaining;
remaining.reserve(edge_ids.size() - matching.size());
for (int edge : edge_ids) {
if (_used_stamp[edge] != _stamp) remaining.push_back(edge);
}
color_regular(remaining, degree - 1, offset + 1);
return;
}
auto [first, second] = split_even(edge_ids);
color_regular(first, degree / 2, offset);
color_regular(second, degree / 2, offset + degree / 2);
}
public:
BipartiteEdgeColoringSolver(
int side_size,
int original_edge_count,
std::vector<int> left,
std::vector<int> right
)
: _side_size(side_size),
_original_edge_count(original_edge_count),
_left(std::move(left)),
_right(std::move(right)),
_color(original_edge_count, -1),
_used_stamp(_left.size(), 0),
_stamp(0) {}
std::vector<int> solve(int degree) {
std::vector<int> edge_ids(_left.size());
for (int edge = 0; edge < int(edge_ids.size()); edge++) edge_ids[edge] = edge;
color_regular(edge_ids, degree, 0);
for (int color : _color) assert(0 <= color && color < degree);
return _color;
}
};
} // namespace detail
// Returns an optimal edge coloring of a bipartite multigraph.
inline BipartiteEdgeColoringResult bipartite_edge_coloring(
int left_size,
int right_size,
const std::vector<std::pair<int, int>>& edges
) {
assert(left_size >= 0);
assert(right_size >= 0);
assert(edges.size() <= std::size_t(std::numeric_limits<int>::max()));
std::vector<int> left_degree(left_size, 0);
std::vector<int> right_degree(right_size, 0);
int maximum_degree = 0;
for (auto [left, right] : edges) {
assert(0 <= left && left < left_size);
assert(0 <= right && right < right_size);
left_degree[left]++;
right_degree[right]++;
maximum_degree = std::max(maximum_degree, left_degree[left]);
maximum_degree = std::max(maximum_degree, right_degree[right]);
}
BipartiteEdgeColoringResult result;
result.color_count = maximum_degree;
if (edges.empty()) return result;
detail::BipartiteEdgeColoringGroups left_groups =
detail::group_vertices(left_degree, maximum_degree);
detail::BipartiteEdgeColoringGroups right_groups =
detail::group_vertices(right_degree, maximum_degree);
int side_size = std::max(left_groups.count, right_groups.count);
std::vector<int> contracted_left;
std::vector<int> contracted_right;
contracted_left.reserve(std::size_t(3) * edges.size());
contracted_right.reserve(std::size_t(3) * edges.size());
std::vector<int> contracted_left_degree(side_size, 0);
std::vector<int> contracted_right_degree(side_size, 0);
for (auto [left, right] : edges) {
int contracted_left_vertex = left_groups.group[left];
int contracted_right_vertex = right_groups.group[right];
contracted_left.push_back(contracted_left_vertex);
contracted_right.push_back(contracted_right_vertex);
contracted_left_degree[contracted_left_vertex]++;
contracted_right_degree[contracted_right_vertex]++;
}
int left = 0;
int right = 0;
while (true) {
while (left < side_size && contracted_left_degree[left] == maximum_degree) left++;
while (right < side_size && contracted_right_degree[right] == maximum_degree) right++;
if (left == side_size || right == side_size) break;
contracted_left.push_back(left);
contracted_right.push_back(right);
contracted_left_degree[left]++;
contracted_right_degree[right]++;
}
assert(left == side_size && right == side_size);
assert(contracted_left.size() == std::size_t(side_size) * std::size_t(maximum_degree));
detail::BipartiteEdgeColoringSolver solver(
side_size,
int(edges.size()),
std::move(contracted_left),
std::move(contracted_right)
);
result.color = solver.solve(maximum_degree);
return result;
}
} // namespace graph
} // namespace m1une
#line 11 "graph/dag_path_cover.hpp"
namespace m1une {
namespace graph {
struct DagPathCoverResult {
std::vector<std::vector<int>> paths;
std::vector<std::vector<int>> path_edge_ids;
std::vector<int> predecessor;
std::vector<int> successor;
std::vector<int> predecessor_edge;
std::vector<int> successor_edge;
int size() const {
return int(paths.size());
}
};
template <class T>
std::optional<DagPathCoverResult> minimum_dag_path_cover(const Graph<T>& g) {
const int n = g.size();
if (!topological_sort(g)) return std::nullopt;
BipartiteMatching matching(n, n);
std::vector<int> original_edge_id;
for (int v = 0; v < n; v++) {
for (const auto& e : g[v]) {
if (!e.alive) continue;
matching.add_edge(v, e.to);
original_edge_id.push_back(e.id);
}
}
DagPathCoverResult result;
result.predecessor.assign(n, -1);
result.successor.assign(n, -1);
result.predecessor_edge.assign(n, -1);
result.successor_edge.assign(n, -1);
for (const auto& pair : matching.matching()) {
const int edge_id = original_edge_id[pair.edge_id];
result.successor[pair.left] = pair.right;
result.successor_edge[pair.left] = edge_id;
result.predecessor[pair.right] = pair.left;
result.predecessor_edge[pair.right] = edge_id;
}
int covered = 0;
for (int s = 0; s < n; s++) {
if (result.predecessor[s] != -1) continue;
result.paths.emplace_back();
result.path_edge_ids.emplace_back();
for (int v = s; v != -1; v = result.successor[v]) {
result.paths.back().push_back(v);
covered++;
if (result.successor_edge[v] != -1) {
result.path_edge_ids.back().push_back(result.successor_edge[v]);
}
}
}
assert(covered == n);
return result;
}
} // namespace graph
} // namespace m1une
#line 1 "graph/dag_reachability.hpp"
#line 9 "graph/dag_reachability.hpp"
#line 1 "utilities/dynamic_bitset.hpp"
#line 9 "utilities/dynamic_bitset.hpp"
namespace m1une {
namespace utilities {
struct DynamicBitset {
private:
static constexpr int BITS_PER_BLOCK = 64;
static constexpr uint64_t FULL_BLOCK = ~uint64_t{0};
int _n;
std::vector<uint64_t> blocks;
static int block_count(int n) {
assert(n >= 0);
return (n + BITS_PER_BLOCK - 1) >> 6;
}
uint64_t tail_mask() const {
const int rem = _n & (BITS_PER_BLOCK - 1);
return rem == 0 ? FULL_BLOCK : ((uint64_t{1} << rem) - 1);
}
// Keep unused bits in the last block equal to zero.
void clean() {
if (!blocks.empty()) blocks.back() &= tail_mask();
}
public:
DynamicBitset() : _n(0), blocks() {}
explicit DynamicBitset(int n, bool val = false) : _n(n), blocks(block_count(n), val ? FULL_BLOCK : 0) {
if (val) clean();
}
// Returns the logical number of bits.
int size() const {
return _n;
}
// Returns whether the bit at index i is set.
bool test(int i) const {
assert(0 <= i && i < _n);
return (blocks[i >> 6] >> (i & (BITS_PER_BLOCK - 1))) & 1;
}
// Sets the bit at index i to true.
void set(int i) {
assert(0 <= i && i < _n);
blocks[i >> 6] |= uint64_t{1} << (i & (BITS_PER_BLOCK - 1));
}
// Sets all bits to true.
void set() {
std::fill(blocks.begin(), blocks.end(), FULL_BLOCK);
clean();
}
// Sets the bit at index i to false.
void reset(int i) {
assert(0 <= i && i < _n);
blocks[i >> 6] &= ~(uint64_t{1} << (i & (BITS_PER_BLOCK - 1)));
}
// Sets all bits to false.
void reset() {
std::fill(blocks.begin(), blocks.end(), uint64_t{0});
}
// Flips the bit at index i.
void flip(int i) {
assert(0 <= i && i < _n);
blocks[i >> 6] ^= uint64_t{1} << (i & (BITS_PER_BLOCK - 1));
}
// Flips all bits.
void flip() {
for (uint64_t& block : blocks) block = ~block;
clean();
}
// Returns the number of set bits.
int popcount() const {
int res = 0;
for (uint64_t block : blocks) res += __builtin_popcountll(block);
return res;
}
// Returns the index of the least significant set bit, or -1 if no bit is set.
int lowbit() const {
const int m = static_cast<int>(blocks.size());
for (int i = 0; i < m; ++i) {
if (blocks[i] != 0) return (i << 6) + __builtin_ctzll(blocks[i]);
}
return -1;
}
// Returns the index of the most significant set bit, or -1 if no bit is set.
int topbit() const {
for (int i = static_cast<int>(blocks.size()) - 1; i >= 0; --i) {
if (blocks[i] != 0) return (i << 6) + (BITS_PER_BLOCK - 1 - __builtin_clzll(blocks[i]));
}
return -1;
}
// Returns whether at least one bit is set.
bool any() const {
for (uint64_t block : blocks) {
if (block != 0) return true;
}
return false;
}
// Returns whether every logical bit is set.
bool all() const {
if (_n == 0) return true;
const int m = static_cast<int>(blocks.size());
for (int i = 0; i + 1 < m; ++i) {
if (blocks[i] != FULL_BLOCK) return false;
}
return blocks.back() == tail_mask();
}
// Returns whether no bit is set.
bool none() const {
return !any();
}
DynamicBitset& operator&=(const DynamicBitset& other) {
assert(_n == other._n);
const std::size_t m = blocks.size();
for (std::size_t i = 0; i < m; ++i) blocks[i] &= other.blocks[i];
return *this;
}
DynamicBitset& operator|=(const DynamicBitset& other) {
assert(_n == other._n);
const std::size_t m = blocks.size();
for (std::size_t i = 0; i < m; ++i) blocks[i] |= other.blocks[i];
return *this;
}
DynamicBitset& operator^=(const DynamicBitset& other) {
assert(_n == other._n);
const std::size_t m = blocks.size();
for (std::size_t i = 0; i < m; ++i) blocks[i] ^= other.blocks[i];
return *this;
}
DynamicBitset operator~() const {
DynamicBitset res = *this;
res.flip();
return res;
}
friend DynamicBitset operator&(DynamicBitset lhs, const DynamicBitset& rhs) {
lhs &= rhs;
return lhs;
}
friend DynamicBitset operator|(DynamicBitset lhs, const DynamicBitset& rhs) {
lhs |= rhs;
return lhs;
}
friend DynamicBitset operator^(DynamicBitset lhs, const DynamicBitset& rhs) {
lhs ^= rhs;
return lhs;
}
};
} // namespace utilities
} // namespace m1une
#line 13 "graph/dag_reachability.hpp"
namespace m1une {
namespace graph {
struct DagReachability {
std::vector<utilities::DynamicBitset> reachable_vertices;
std::vector<int> topological_order;
int size() const {
return int(reachable_vertices.size());
}
bool reachable(int from, int to) const {
assert(0 <= from && from < size());
assert(0 <= to && to < size());
return reachable_vertices[from].test(to);
}
};
template <class T>
std::optional<DagReachability> dag_reachability(const Graph<T>& g) {
const int n = g.size();
auto order = topological_sort(g);
if (!order) return std::nullopt;
DagReachability result;
result.reachable_vertices.assign(n, utilities::DynamicBitset(n));
result.topological_order = *order;
for (int i = n - 1; i >= 0; i--) {
int v = (*order)[i];
result.reachable_vertices[v].set(v);
for (const auto& e : g[v]) {
if (e.alive) result.reachable_vertices[v] |= result.reachable_vertices[e.to];
}
}
return result;
}
template <class T>
struct DagTransitiveReductionResult {
Graph<T> graph;
std::vector<int> original_edge_ids;
};
template <class T>
std::optional<DagTransitiveReductionResult<T>> dag_transitive_reduction(const Graph<T>& g) {
auto reachability = dag_reachability(g);
if (!reachability) return std::nullopt;
const int n = g.size();
std::vector<int> position(n);
for (int i = 0; i < n; i++) position[reachability->topological_order[i]] = i;
std::vector<char> kept(g.edge_count(), false);
for (int v = 0; v < n; v++) {
std::vector<const Edge<T>*> outgoing;
outgoing.reserve(g[v].size());
for (const auto& e : g[v]) {
if (e.alive) outgoing.push_back(&e);
}
std::stable_sort(outgoing.begin(), outgoing.end(), [&](const auto* lhs, const auto* rhs) {
return position[lhs->to] < position[rhs->to];
});
utilities::DynamicBitset covered(n);
for (const auto* e : outgoing) {
if (covered.test(e->to)) continue;
kept[e->id] = true;
covered |= reachability->reachable_vertices[e->to];
}
}
DagTransitiveReductionResult<T> result;
result.graph = Graph<T>(n);
for (int v = 0; v < n; v++) {
for (const auto& e : g[v]) {
if (!e.alive || !kept[e.id]) continue;
result.graph.add_directed_edge(e.from, e.to, e.cost);
result.original_edge_ids.push_back(e.id);
}
}
return result;
}
} // namespace graph
} // namespace m1une
#line 1 "graph/dag_shortest_path.hpp"
#line 9 "graph/dag_shortest_path.hpp"
#line 12 "graph/dag_shortest_path.hpp"
namespace m1une {
namespace graph {
template <class T>
struct DagShortestPathResult {
std::vector<T> dist;
std::vector<int> parent;
std::vector<int> parent_edge;
std::vector<int> topological_order;
T inf;
bool reachable(int v) const {
assert(0 <= v && v < int(dist.size()));
return dist[v] != inf;
}
std::vector<int> path(int t) const {
assert(reachable(t));
std::vector<int> result;
for (int v = t; v != -1; v = parent[v]) result.push_back(v);
std::reverse(result.begin(), result.end());
return result;
}
};
template <class T>
std::optional<DagShortestPathResult<T>> dag_shortest_path(
const Graph<T>& g, const std::vector<int>& sources, T inf = std::numeric_limits<T>::max() / T(4)) {
int n = g.size();
auto order = topological_sort(g);
if (!order) return std::nullopt;
DagShortestPathResult<T> result;
result.dist.assign(n, inf);
result.parent.assign(n, -1);
result.parent_edge.assign(n, -1);
result.topological_order = *order;
result.inf = inf;
for (int s : sources) {
assert(0 <= s && s < n);
if (result.dist[s] == T(0)) continue;
result.dist[s] = T(0);
}
for (int v : *order) {
if (result.dist[v] == inf) continue;
for (const auto& e : g[v]) {
if (!e.alive) continue;
T nd = result.dist[v] + e.cost;
if (result.dist[e.to] <= nd) continue;
result.dist[e.to] = nd;
result.parent[e.to] = v;
result.parent_edge[e.to] = e.id;
}
}
return result;
}
template <class T>
std::optional<DagShortestPathResult<T>> dag_shortest_path(
const Graph<T>& g, int s, T inf = std::numeric_limits<T>::max() / T(4)) {
return dag_shortest_path(g, std::vector<int>{s}, inf);
}
} // namespace graph
} // namespace m1une
#line 10 "graph/dag.hpp"