library

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

View the Project on GitHub gyouzasushi/library

:heavy_check_mark: test/unit/quotient_graph.test.cpp

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <set>
#include <vector>

#include "atcoder/scc"
#include "graph/lowlink.hpp"
#include "graph/quotient_graph.hpp"
int main() {
    std::mt19937 rng(20261029);
    for (int trial = 0; trial < 2000; trial++) {
        int n = 1 + rng() % 8;
        int m = rng() % 16;
        atcoder::scc_graph sg(n);
        std::vector<std::vector<int>> g(n);
        std::vector<std::vector<bool>> reach(n, std::vector<bool>(n, false));
        for (int i = 0; i < n; i++) reach[i][i] = true;
        for (int i = 0; i < m; i++) {
            int u = rng() % n, v = rng() % n;
            sg.add_edge(u, v);
            g[u].push_back(v);
            reach[u][v] = 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]);
            }
        }
        std::vector<std::vector<int>> scc = sg.scc();
        std::vector<int> id = component_id(n, scc);
        std::vector<std::vector<int>> dag = quotient_graph(g, scc);
        int k = int(scc.size());
        assert(int(dag.size()) == k);
        for (int u = 0; u < n; u++) {
            assert(0 <= id[u] && id[u] < k);
            for (int v = 0; v < n; v++) assert((id[u] == id[v]) == (reach[u][v] && reach[v][u]));
            for (int v : g[u]) assert(id[u] <= id[v]);
        }
        for (int i = 0; i < k; i++) {
            for (int v : scc[i]) assert(id[v] == i);
        }
        std::vector<std::set<int>> expect(k);
        for (int u = 0; u < n; u++) {
            for (int v : g[u]) {
                if (id[u] != id[v]) expect[id[u]].insert(id[v]);
            }
        }
        for (int i = 0; i < k; i++) {
            assert(dag[i] == std::vector<int>(expect[i].begin(), expect[i].end()));
            for (int j : dag[i]) assert(i < j);
        }
    }
    for (int trial = 0; trial < 2000; trial++) {
        int n = 1 + rng() % 8;
        int m = rng() % 12;
        lowlink lk(n);
        std::vector<std::vector<int>> g(n);
        for (int i = 0; i < m; i++) {
            int u = rng() % n, v = rng() % n;
            lk.add_edge(u, v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        lk.build();
        std::vector<std::vector<int>> comps = lk.two_edge_connected_components();
        std::vector<int> id = component_id(n, comps);
        std::vector<std::vector<int>> tree = quotient_graph(g, comps);
        int k = int(comps.size());
        int edges = 0;
        for (int i = 0; i < k; i++) {
            edges += int(tree[i].size());
            for (int j : tree[i]) assert(std::ranges::binary_search(tree[j], i));
        }
        assert(edges == 2 * int(lk.bridges().size()));
        for (int v = 0; v < n; v++) assert(id[v] == lk.component(v));
    }
    std::cout << "Hello World\n";
}
#line 1 "test/unit/quotient_graph.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <set>
#include <vector>

#line 1 "atcoder/scc.hpp"



#line 7 "atcoder/scc.hpp"

#line 1 "atcoder/internal_scc.hpp"



#line 5 "atcoder/internal_scc.hpp"
#include <utility>
#line 7 "atcoder/internal_scc.hpp"

#line 1 "atcoder/internal_csr.hpp"



#line 7 "atcoder/internal_csr.hpp"

namespace atcoder {
namespace internal {

template <class E> struct csr {
    std::vector<int> start;
    std::vector<E> elist;
    explicit csr(int n, const std::vector<std::pair<int, E>>& edges)
        : start(n + 1), elist(edges.size()) {
        for (auto e : edges) {
            start[e.first + 1]++;
        }
        for (int i = 1; i <= n; i++) {
            start[i] += start[i - 1];
        }
        auto counter = start;
        for (auto e : edges) {
            elist[counter[e.first]++] = e.second;
        }
    }
};

}  // namespace internal

}  // namespace atcoder


#line 9 "atcoder/internal_scc.hpp"

namespace atcoder {
namespace internal {

// Reference:
// R. Tarjan,
// Depth-First Search and Linear Graph Algorithms
struct scc_graph {
  public:
    explicit scc_graph(int n) : _n(n) {}

    int num_vertices() { return _n; }

    void add_edge(int from, int to) { edges.push_back({from, {to}}); }

    // @return pair of (# of scc, scc id)
    std::pair<int, std::vector<int>> scc_ids() {
        auto g = csr<edge>(_n, edges);
        int now_ord = 0, group_num = 0;
        std::vector<int> visited, low(_n), ord(_n, -1), ids(_n);
        visited.reserve(_n);
        auto dfs = [&](auto self, int v) -> void {
            low[v] = ord[v] = now_ord++;
            visited.push_back(v);
            for (int i = g.start[v]; i < g.start[v + 1]; i++) {
                auto to = g.elist[i].to;
                if (ord[to] == -1) {
                    self(self, to);
                    low[v] = std::min(low[v], low[to]);
                } else {
                    low[v] = std::min(low[v], ord[to]);
                }
            }
            if (low[v] == ord[v]) {
                while (true) {
                    int u = visited.back();
                    visited.pop_back();
                    ord[u] = _n;
                    ids[u] = group_num;
                    if (u == v) break;
                }
                group_num++;
            }
        };
        for (int i = 0; i < _n; i++) {
            if (ord[i] == -1) dfs(dfs, i);
        }
        for (auto& x : ids) {
            x = group_num - 1 - x;
        }
        return {group_num, ids};
    }

    std::vector<std::vector<int>> scc() {
        auto ids = scc_ids();
        int group_num = ids.first;
        std::vector<int> counts(group_num);
        for (auto x : ids.second) counts[x]++;
        std::vector<std::vector<int>> groups(ids.first);
        for (int i = 0; i < group_num; i++) {
            groups[i].reserve(counts[i]);
        }
        for (int i = 0; i < _n; i++) {
            groups[ids.second[i]].push_back(i);
        }
        return groups;
    }

  private:
    int _n;
    struct edge {
        int to;
    };
    std::vector<std::pair<int, edge>> edges;
};

}  // namespace internal

}  // namespace atcoder


#line 9 "atcoder/scc.hpp"

namespace atcoder {

struct scc_graph {
  public:
    scc_graph() : internal(0) {}
    explicit scc_graph(int n) : internal(n) {}

    void add_edge(int from, int to) {
        int n = internal.num_vertices();
        assert(0 <= from && from < n);
        assert(0 <= to && to < n);
        internal.add_edge(from, to);
    }

    std::vector<std::vector<int>> scc() { return internal.scc(); }

  private:
    internal::scc_graph internal;
};

}  // namespace atcoder


#line 6 "graph/lowlink.hpp"
struct lowlink {
public:
    lowlink() : lowlink(0) {
    }
    explicit lowlink(int n) : _n(n), g(n), ord(n, -1), low(n), comp(n, -1), art(n, false) {
    }
    int add_edge(int u, int v) {
        assert(0 <= u && u < _n);
        assert(0 <= v && v < _n);
        int e = int(edges.size());
        edges.emplace_back(u, v);
        g[u].emplace_back(v, e);
        g[v].emplace_back(u, e);
        return e;
    }
    void build() {
        int m = int(edges.size());
        bridge.assign(m, false);
        std::vector<int> it(_n, 0), par_edge(_n, -1), children(_n, 0);
        int t = 0;
        for (int r = 0; r < _n; r++) {
            if (ord[r] != -1) continue;
            std::vector<int> st = {r};
            ord[r] = low[r] = t++;
            while (!st.empty()) {
                int v = st.back();
                if (it[v] < int(g[v].size())) {
                    auto [u, e] = g[v][it[v]++];
                    if (e == par_edge[v]) continue;
                    if (ord[u] == -1) {
                        ord[u] = low[u] = t++;
                        par_edge[u] = e;
                        children[v]++;
                        st.push_back(u);
                    } else {
                        low[v] = std::min(low[v], ord[u]);
                    }
                } else {
                    st.pop_back();
                    if (st.empty()) continue;
                    int p = st.back();
                    low[p] = std::min(low[p], low[v]);
                    if (low[v] > ord[p]) bridge[par_edge[v]] = true;
                    if (low[v] >= ord[p] && p != r) art[p] = true;
                }
            }
            art[r] = children[r] >= 2;
        }
        _num_components = 0;
        for (int r = 0; r < _n; r++) {
            if (comp[r] != -1) continue;
            comp[r] = _num_components;
            std::vector<int> st = {r};
            while (!st.empty()) {
                int v = st.back();
                st.pop_back();
                for (auto [u, e] : g[v]) {
                    if (bridge[e] || comp[u] != -1) continue;
                    comp[u] = _num_components;
                    st.push_back(u);
                }
            }
            _num_components++;
        }
    }
    bool is_bridge(int e) const {
        assert(0 <= e && e < int(edges.size()));
        return bridge[e];
    }
    bool is_articulation(int v) const {
        assert(0 <= v && v < _n);
        return art[v];
    }
    std::vector<int> bridges() const {
        std::vector<int> res;
        for (int e = 0; e < int(edges.size()); e++) {
            if (bridge[e]) res.push_back(e);
        }
        return res;
    }
    std::vector<int> articulation_points() const {
        std::vector<int> res;
        for (int v = 0; v < _n; v++) {
            if (art[v]) res.push_back(v);
        }
        return res;
    }
    int component(int v) const {
        assert(0 <= v && v < _n);
        return comp[v];
    }
    std::vector<std::vector<int>> two_edge_connected_components() const {
        std::vector<std::vector<int>> res(_num_components);
        for (int v = 0; v < _n; v++) res[comp[v]].push_back(v);
        return res;
    }

private:
    int _n, _num_components = 0;
    std::vector<std::vector<std::pair<int, int>>> g;
    std::vector<std::pair<int, int>> edges;
    std::vector<int> ord, low, comp;
    std::vector<bool> art, bridge;
};
#line 4 "graph/quotient_graph.hpp"
inline std::vector<int> component_id(int n, const std::vector<std::vector<int>>& groups) {
    std::vector<int> id(n);
    for (int i = 0; i < int(groups.size()); i++) {
        for (int v : groups[i]) id[v] = i;
    }
    return id;
}
inline std::vector<std::vector<int>> quotient_graph(const std::vector<std::vector<int>>& g, const std::vector<std::vector<int>>& groups) {
    std::vector<int> id = component_id(int(g.size()), groups);
    std::vector<std::vector<int>> q(groups.size());
    for (int u = 0; u < int(g.size()); u++) {
        for (int v : g[u]) {
            if (id[u] != id[v]) q[id[u]].push_back(id[v]);
        }
    }
    for (auto& es : q) {
        std::ranges::sort(es);
        es.erase(std::ranges::unique(es).begin(), es.end());
    }
    return q;
}
#line 12 "test/unit/quotient_graph.test.cpp"
int main() {
    std::mt19937 rng(20261029);
    for (int trial = 0; trial < 2000; trial++) {
        int n = 1 + rng() % 8;
        int m = rng() % 16;
        atcoder::scc_graph sg(n);
        std::vector<std::vector<int>> g(n);
        std::vector<std::vector<bool>> reach(n, std::vector<bool>(n, false));
        for (int i = 0; i < n; i++) reach[i][i] = true;
        for (int i = 0; i < m; i++) {
            int u = rng() % n, v = rng() % n;
            sg.add_edge(u, v);
            g[u].push_back(v);
            reach[u][v] = 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]);
            }
        }
        std::vector<std::vector<int>> scc = sg.scc();
        std::vector<int> id = component_id(n, scc);
        std::vector<std::vector<int>> dag = quotient_graph(g, scc);
        int k = int(scc.size());
        assert(int(dag.size()) == k);
        for (int u = 0; u < n; u++) {
            assert(0 <= id[u] && id[u] < k);
            for (int v = 0; v < n; v++) assert((id[u] == id[v]) == (reach[u][v] && reach[v][u]));
            for (int v : g[u]) assert(id[u] <= id[v]);
        }
        for (int i = 0; i < k; i++) {
            for (int v : scc[i]) assert(id[v] == i);
        }
        std::vector<std::set<int>> expect(k);
        for (int u = 0; u < n; u++) {
            for (int v : g[u]) {
                if (id[u] != id[v]) expect[id[u]].insert(id[v]);
            }
        }
        for (int i = 0; i < k; i++) {
            assert(dag[i] == std::vector<int>(expect[i].begin(), expect[i].end()));
            for (int j : dag[i]) assert(i < j);
        }
    }
    for (int trial = 0; trial < 2000; trial++) {
        int n = 1 + rng() % 8;
        int m = rng() % 12;
        lowlink lk(n);
        std::vector<std::vector<int>> g(n);
        for (int i = 0; i < m; i++) {
            int u = rng() % n, v = rng() % n;
            lk.add_edge(u, v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        lk.build();
        std::vector<std::vector<int>> comps = lk.two_edge_connected_components();
        std::vector<int> id = component_id(n, comps);
        std::vector<std::vector<int>> tree = quotient_graph(g, comps);
        int k = int(comps.size());
        int edges = 0;
        for (int i = 0; i < k; i++) {
            edges += int(tree[i].size());
            for (int j : tree[i]) assert(std::ranges::binary_search(tree[j], i));
        }
        assert(edges == 2 * int(lk.bridges().size()));
        for (int v = 0; v < n; v++) assert(id[v] == lk.component(v));
    }
    std::cout << "Hello World\n";
}
Back to top page