m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

View on GitHub

:heavy_check_mark: verify/graph/dag_algorithms.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_4_A"

#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <limits>
#include <random>
#include <vector>

#include "../../graph/dag.hpp"

using m1une::graph::Graph;

std::vector<std::vector<char>> naive_reachability(const Graph<int>& g) {
    const int n = g.size();
    std::vector<std::vector<char>> reach(n, std::vector<char>(n, false));
    for (int v = 0; v < n; v++) reach[v][v] = true;
    for (int v = 0; v < n; v++) {
        for (const auto& e : g[v]) {
            if (e.alive) reach[v][e.to] = true;
        }
    }
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
            }
        }
    }
    return reach;
}

int naive_maximum_matching(const Graph<int>& g) {
    const int n = g.size();
    std::vector<std::vector<int>> adjacency(n);
    for (int v = 0; v < n; v++) {
        for (const auto& e : g[v]) {
            if (e.alive && std::find(adjacency[v].begin(), adjacency[v].end(), e.to) == adjacency[v].end()) {
                adjacency[v].push_back(e.to);
            }
        }
    }

    std::vector<int> dp(1 << n, -1);
    dp[0] = 0;
    for (int left = 0; left < n; left++) {
        std::vector<int> next = dp;
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] < 0) continue;
            for (int right : adjacency[left]) {
                if ((mask >> right) & 1) continue;
                int next_mask = mask | (1 << right);
                next[next_mask] = std::max(next[next_mask], dp[mask] + 1);
            }
        }
        dp.swap(next);
    }
    return *std::max_element(dp.begin(), dp.end());
}

void test_randomized() {
    std::mt19937 rng(123456789);
    for (int iteration = 0; iteration < 1000; iteration++) {
        const int n = int(rng() % 8);
        std::vector<int> order(n);
        for (int i = 0; i < n; i++) order[i] = i;
        std::shuffle(order.begin(), order.end(), rng);

        Graph<int> g(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (rng() % 3 != 0) continue;
                g.add_directed_edge(order[i], order[j], int(rng() % 11) - 5);
                if (rng() % 8 == 0) {
                    int id = g.add_directed_edge(order[i], order[j], int(rng() % 11) - 5);
                    if (rng() % 3 == 0) g.erase_edge(id);
                }
            }
        }

        std::vector<int> sources;
        for (int v = 0; v < n; v++) {
            if (rng() % 3 == 0) sources.push_back(v);
        }
        if (n > 0 && sources.empty()) sources.push_back(int(rng() % n));

        const int neg_inf = std::numeric_limits<int>::lowest() / 4;
        std::vector<int> longest(n, neg_inf);
        std::vector<long long> path_count(n, 0);
        std::function<void(int, int)> enumerate = [&](int v, int distance) {
            longest[v] = std::max(longest[v], distance);
            path_count[v]++;
            for (const auto& e : g[v]) {
                if (e.alive) enumerate(e.to, distance + e.cost);
            }
        };
        for (int s : sources) enumerate(s, 0);

        auto longest_result = m1une::graph::dag_longest_path(g, sources);
        assert(longest_result.has_value());
        assert(longest_result->dist == longest);
        for (int v = 0; v < n; v++) {
            if (!longest_result->reachable(v)) continue;
            std::vector<int> path = longest_result->path(v);
            assert(!path.empty() && path.back() == v);
            assert(std::find(sources.begin(), sources.end(), path.front()) != sources.end());
        }

        auto count_result = m1une::graph::dag_path_count<long long>(g, sources);
        assert(count_result.has_value());
        assert(*count_result == path_count);

        auto reachability = m1une::graph::dag_reachability(g);
        assert(reachability.has_value());
        auto expected_reachability = naive_reachability(g);
        for (int from = 0; from < n; from++) {
            for (int to = 0; to < n; to++) {
                assert(reachability->reachable(from, to) == bool(expected_reachability[from][to]));
            }
        }

        auto reduction = m1une::graph::dag_transitive_reduction(g);
        assert(reduction.has_value());
        assert(naive_reachability(reduction->graph) == expected_reachability);
        assert(reduction->graph.edge_count() == int(reduction->original_edge_ids.size()));
        std::vector<m1une::graph::Edge<int>> reduced_edges = reduction->graph.edges();
        for (int removed = 0; removed < reduction->graph.edge_count(); removed++) {
            Graph<int> without_edge(n);
            for (const auto& e : reduced_edges) {
                if (e.id != removed) without_edge.add_directed_edge(e.from, e.to, e.cost);
            }
            const auto& edge = reduced_edges[removed];
            assert(!naive_reachability(without_edge)[edge.from][edge.to]);
        }

        auto cover = m1une::graph::minimum_dag_path_cover(g);
        assert(cover.has_value());
        assert(cover->size() == n - naive_maximum_matching(g));
        std::vector<int> occurrence(n, 0);
        for (int i = 0; i < cover->size(); i++) {
            assert(cover->path_edge_ids[i].size() + 1 == cover->paths[i].size());
            for (int v : cover->paths[i]) occurrence[v]++;
            for (int j = 0; j + 1 < int(cover->paths[i].size()); j++) {
                int from = cover->paths[i][j];
                int to = cover->paths[i][j + 1];
                int edge_id = cover->path_edge_ids[i][j];
                bool found = false;
                for (const auto& e : g[from]) {
                    if (e.alive && e.to == to && e.id == edge_id) found = true;
                }
                assert(found);
            }
        }
        for (int count : occurrence) assert(count == 1);
    }
}

void test_cycle_rejection() {
    Graph<int> g(3);
    g.add_directed_edge(0, 1);
    g.add_directed_edge(1, 2);
    g.add_directed_edge(2, 0);
    assert(!m1une::graph::dag_longest_path(g, 0));
    assert(!m1une::graph::dag_path_count(g, 0));
    assert(!m1une::graph::dag_reachability(g));
    assert(!m1une::graph::dag_transitive_reduction(g));
    assert(!m1une::graph::minimum_dag_path_cover(g));
}

int main() {
    test_randomized();
    test_cycle_rejection();

    int vertex_count, edge_count;
    std::cin >> vertex_count >> edge_count;
    Graph<int> g(vertex_count);
    for (int i = 0; i < edge_count; i++) {
        int from, to;
        std::cin >> from >> to;
        g.add_directed_edge(from, to);
    }
    std::cout << !m1une::graph::is_dag(g) << '\n';
}
#line 1 "verify/graph/dag_algorithms.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/GRL_4_A"

#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <limits>
#include <random>
#include <vector>

#line 1 "graph/dag.hpp"



#line 1 "graph/dag_longest_path.hpp"



#line 7 "graph/dag_longest_path.hpp"
#include <optional>
#line 9 "graph/dag_longest_path.hpp"

#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"


#line 12 "verify/graph/dag_algorithms.test.cpp"

using m1une::graph::Graph;

std::vector<std::vector<char>> naive_reachability(const Graph<int>& g) {
    const int n = g.size();
    std::vector<std::vector<char>> reach(n, std::vector<char>(n, false));
    for (int v = 0; v < n; v++) reach[v][v] = true;
    for (int v = 0; v < n; v++) {
        for (const auto& e : g[v]) {
            if (e.alive) reach[v][e.to] = true;
        }
    }
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
            }
        }
    }
    return reach;
}

int naive_maximum_matching(const Graph<int>& g) {
    const int n = g.size();
    std::vector<std::vector<int>> adjacency(n);
    for (int v = 0; v < n; v++) {
        for (const auto& e : g[v]) {
            if (e.alive && std::find(adjacency[v].begin(), adjacency[v].end(), e.to) == adjacency[v].end()) {
                adjacency[v].push_back(e.to);
            }
        }
    }

    std::vector<int> dp(1 << n, -1);
    dp[0] = 0;
    for (int left = 0; left < n; left++) {
        std::vector<int> next = dp;
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] < 0) continue;
            for (int right : adjacency[left]) {
                if ((mask >> right) & 1) continue;
                int next_mask = mask | (1 << right);
                next[next_mask] = std::max(next[next_mask], dp[mask] + 1);
            }
        }
        dp.swap(next);
    }
    return *std::max_element(dp.begin(), dp.end());
}

void test_randomized() {
    std::mt19937 rng(123456789);
    for (int iteration = 0; iteration < 1000; iteration++) {
        const int n = int(rng() % 8);
        std::vector<int> order(n);
        for (int i = 0; i < n; i++) order[i] = i;
        std::shuffle(order.begin(), order.end(), rng);

        Graph<int> g(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (rng() % 3 != 0) continue;
                g.add_directed_edge(order[i], order[j], int(rng() % 11) - 5);
                if (rng() % 8 == 0) {
                    int id = g.add_directed_edge(order[i], order[j], int(rng() % 11) - 5);
                    if (rng() % 3 == 0) g.erase_edge(id);
                }
            }
        }

        std::vector<int> sources;
        for (int v = 0; v < n; v++) {
            if (rng() % 3 == 0) sources.push_back(v);
        }
        if (n > 0 && sources.empty()) sources.push_back(int(rng() % n));

        const int neg_inf = std::numeric_limits<int>::lowest() / 4;
        std::vector<int> longest(n, neg_inf);
        std::vector<long long> path_count(n, 0);
        std::function<void(int, int)> enumerate = [&](int v, int distance) {
            longest[v] = std::max(longest[v], distance);
            path_count[v]++;
            for (const auto& e : g[v]) {
                if (e.alive) enumerate(e.to, distance + e.cost);
            }
        };
        for (int s : sources) enumerate(s, 0);

        auto longest_result = m1une::graph::dag_longest_path(g, sources);
        assert(longest_result.has_value());
        assert(longest_result->dist == longest);
        for (int v = 0; v < n; v++) {
            if (!longest_result->reachable(v)) continue;
            std::vector<int> path = longest_result->path(v);
            assert(!path.empty() && path.back() == v);
            assert(std::find(sources.begin(), sources.end(), path.front()) != sources.end());
        }

        auto count_result = m1une::graph::dag_path_count<long long>(g, sources);
        assert(count_result.has_value());
        assert(*count_result == path_count);

        auto reachability = m1une::graph::dag_reachability(g);
        assert(reachability.has_value());
        auto expected_reachability = naive_reachability(g);
        for (int from = 0; from < n; from++) {
            for (int to = 0; to < n; to++) {
                assert(reachability->reachable(from, to) == bool(expected_reachability[from][to]));
            }
        }

        auto reduction = m1une::graph::dag_transitive_reduction(g);
        assert(reduction.has_value());
        assert(naive_reachability(reduction->graph) == expected_reachability);
        assert(reduction->graph.edge_count() == int(reduction->original_edge_ids.size()));
        std::vector<m1une::graph::Edge<int>> reduced_edges = reduction->graph.edges();
        for (int removed = 0; removed < reduction->graph.edge_count(); removed++) {
            Graph<int> without_edge(n);
            for (const auto& e : reduced_edges) {
                if (e.id != removed) without_edge.add_directed_edge(e.from, e.to, e.cost);
            }
            const auto& edge = reduced_edges[removed];
            assert(!naive_reachability(without_edge)[edge.from][edge.to]);
        }

        auto cover = m1une::graph::minimum_dag_path_cover(g);
        assert(cover.has_value());
        assert(cover->size() == n - naive_maximum_matching(g));
        std::vector<int> occurrence(n, 0);
        for (int i = 0; i < cover->size(); i++) {
            assert(cover->path_edge_ids[i].size() + 1 == cover->paths[i].size());
            for (int v : cover->paths[i]) occurrence[v]++;
            for (int j = 0; j + 1 < int(cover->paths[i].size()); j++) {
                int from = cover->paths[i][j];
                int to = cover->paths[i][j + 1];
                int edge_id = cover->path_edge_ids[i][j];
                bool found = false;
                for (const auto& e : g[from]) {
                    if (e.alive && e.to == to && e.id == edge_id) found = true;
                }
                assert(found);
            }
        }
        for (int count : occurrence) assert(count == 1);
    }
}

void test_cycle_rejection() {
    Graph<int> g(3);
    g.add_directed_edge(0, 1);
    g.add_directed_edge(1, 2);
    g.add_directed_edge(2, 0);
    assert(!m1une::graph::dag_longest_path(g, 0));
    assert(!m1une::graph::dag_path_count(g, 0));
    assert(!m1une::graph::dag_reachability(g));
    assert(!m1une::graph::dag_transitive_reduction(g));
    assert(!m1une::graph::minimum_dag_path_cover(g));
}

int main() {
    test_randomized();
    test_cycle_rejection();

    int vertex_count, edge_count;
    std::cin >> vertex_count >> edge_count;
    Graph<int> g(vertex_count);
    for (int i = 0; i < edge_count; i++) {
        int from, to;
        std::cin >> from >> to;
        g.add_directed_edge(from, to);
    }
    std::cout << !m1une::graph::is_dag(g) << '\n';
}
Back to top page