graph/strongly_connected_components.cpp

• View this file on GitHub
• Last update: 2022-03-31 10:32:23+09:00

Depends on

• utility/rec_lambda.cpp
• utility/rep.cpp
• utility/setmin.cpp

Verified with

• test/strongly_connected_components.test.cpp

Code

#pragma once
#include <cassert>
#include <vector>
#include "../utility/rec_lambda.cpp"
#include "../utility/rep.cpp"
#include "../utility/setmin.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 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;
    }
};

Back to top page