test/strongly_connected_components.test.cpp

View this file on GitHub
Last update: 2022-03-31 10:32:23+09:00
Problem: https://judge.yosupo.jp/problem/scc

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/scc"
#include "../graph/strongly_connected_components.cpp"
#include "../graph/basic_graph.cpp"
#include <iostream>

int main() {
    int N, M;
    std::cin >> N >> M;
    BasicGraph graph(N);
    while (M--) {
        int a, b;
        std::cin >> a >> b;
        graph.add_edge(a, b);
    }
    const auto ans = StronglyConnectedComponents(graph).decompose();
    std::cout << ans.size() << '\n';
    for (const auto& v : ans) {
        std::cout << v.size();
        for (const auto x : v) {
            std::cout << ' ' << x;
        }
        std::cout << '\n';
    }
}

#line 1 "test/strongly_connected_components.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/scc"
#line 2 "graph/strongly_connected_components.cpp"
#include <cassert>
#include <vector>
#line 2 "utility/rec_lambda.cpp"
#include <type_traits>
#include <utility>

template <class F> struct RecursiveLambda : private F {
    explicit constexpr RecursiveLambda(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> constexpr decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

template <class F> constexpr decltype(auto) rec_lambda(F&& f) { return RecursiveLambda<F>(std::forward<F>(f)); }
#line 2 "utility/rep.cpp"
#include <algorithm>

class Range {
    struct Iter {
        int itr;
        constexpr Iter(const int pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { ++itr; }
        constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
        constexpr int operator*() const noexcept { return itr; }
    };
    const Iter first, last;

  public:
    explicit constexpr Range(const int first, const int last) noexcept : first(first), last(std::max(first, last)) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

constexpr Range rep(const int l, const int r) noexcept { return Range(l, r); }
constexpr Range rep(const int n) noexcept { return Range(0, n); }
#line 2 "utility/setmin.cpp"

template <class T> constexpr bool setmin(T& lhs, const T& rhs) {
    if (lhs > rhs) {
        lhs = rhs;
        return true;
    }
    return false;
}
#line 7 "graph/strongly_connected_components.cpp"

template <class G> class StronglyConnectedComponents {
    int count;
    std::vector<int> index;

  public:
    StronglyConnectedComponents() : count(0), index() {}
    explicit StronglyConnectedComponents(const G& graph) : count(0), index(graph.size()) {
        const int n = size();
        int time_stamp = 0;
        std::vector<int> visited, low(n), ord(n);
        visited.reserve(n);
        const auto dfs = rec_lambda([&](auto&& dfs, const int u) -> void {
            low[u] = ord[u] = ++time_stamp;
            visited.push_back(u);
            for (const int v : graph[u]) {
                if (!ord[v]) {
                    dfs(v);
                    setmin(low[u], low[v]);
                } else {
                    setmin(low[u], ord[v]);
                }
            }
            if (low[u] == ord[u]) {
                while (true) {
                    const int v = visited.back();
                    visited.pop_back();
                    ord[v] = n;
                    index[v] = count;
                    if (u == v) break;
                }
                count += 1;
            }
        });
        for (const int u : rep(n))
            if (!ord[u]) dfs(u);
        for (auto& x : index) x = count - x - 1;
    }

    int size() const { return index.size(); }
    int group_count() const { return count; }
    int group_id(const int u) const {
        assert(0 <= u and u < size());
        return index[u];
    }

    std::vector<std::vector<int>> decompose() const {
        std::vector<std::vector<int>> ret(group_count());
        std::vector<int> len(group_count());
        for (const int i : index) len[i] += 1;
        for (const int i : rep(0, group_count())) ret[i].reserve(len[i]);
        for (const int u : rep(size())) ret[index[u]].push_back(u);
        return ret;
    }
};
#line 3 "utility/index_offset.cpp"

class IndexOffset {
    int offset, len;

  public:
    constexpr IndexOffset() noexcept : offset(), len() {}
    explicit constexpr IndexOffset(const int o, const int l) noexcept : offset(o), len(l) {}
    constexpr int size() const { return len; }
    constexpr int operator[](const int i) const noexcept {
        assert(i < len);
        return offset + i;
    }
    constexpr int to_idx(const int i) const noexcept {
        assert(offset <= i and i < offset + len);
        return i - offset;
    }
};
#line 6 "graph/basic_graph.cpp"

template <class E = int> class BasicGraph {
    std::vector<std::vector<E>> graph;

  public:
    BasicGraph() : graph() {}
    explicit BasicGraph(const int n) : graph(n) {}

    class EdgePtr {
        friend class BasicGraph;
        int u, e;
        BasicGraph* self;

        explicit EdgePtr(const int u, const int e, BasicGraph* p) : u(u), e(e), self(p) {}

      public:
        EdgePtr() : u(0), e(0), self(nullptr) {}
        int src() const { return u; }
        E& operator*() const { return self->graph[u][e]; }
        E* operator->() const { return &self->graph[u][e]; }
    };

    int size() const { return graph.size(); }
    std::vector<E>& operator[](const int u) {
        assert(0 <= u and u < size());
        return graph[u];
    }
    const std::vector<E>& operator[](const int u) const {
        assert(0 <= u and u < size());
        return graph[u];
    }

    int add_vertex() {
        graph.emplace_back();
        return size() - 1;
    }
    IndexOffset add_vertices(int n) {
        IndexOffset ret(size(), n);
        while (n--) graph.emplace_back();
        return ret;
    }

    template <class... Args> EdgePtr add_edge(const int u, Args&&... args) {
        assert(0 <= u and u < size());
        const int e = graph[u].size();
        graph[u].emplace_back(std::forward<Args>(args)...);
        return EdgePtr(u, e, this);
    }
};
#line 4 "test/strongly_connected_components.test.cpp"
#include <iostream>

int main() {
    int N, M;
    std::cin >> N >> M;
    BasicGraph graph(N);
    while (M--) {
        int a, b;
        std::cin >> a >> b;
        graph.add_edge(a, b);
    }
    const auto ans = StronglyConnectedComponents(graph).decompose();
    std::cout << ans.size() << '\n';
    for (const auto& v : ans) {
        std::cout << v.size();
        for (const auto x : v) {
            std::cout << ' ' << x;
        }
        std::cout << '\n';
    }
}