Strongly connected component decomposition (tools/scc_graph.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2022-06-05 16:52:56+09:00
Include: #include "tools/scc_graph.hpp"

It takes a directed graph with $n$ vertices as input, and decomposes the graph into strongly connected components.

License

Author

anqooqie

Constructor

scc_graph graph(std::size_t n);

It creates a directed graph with $n$ vertices and $0$ edges.

Constraints

$n \geq 0$

Time Complexity

$O(n)$

size

std::size_t graph.size();

It returns $n$.

Constraints

None

Time Complexity

$O(1)$

add_edge

std::size_t graph.add_edge(std::size_t u, std::size_t v);

It adds a directed edge from $u$ to $v$ to the graph, and returns the index of the added edge.

Constraints

graph.build() has not been called ever.
$0 \leq u < n$
$0 \leq v < n$

Time Complexity

$O(1)$ amortized

edge

std::pair<std::size_t, std::size_t> graph.edge(std::size_t i);

It returns the source and destination of the $i$-th edge of the graph.

Constraints

$0 \leq i < m$ where $m$ is the number of edges

Time Complexity

$O(1)$

edges_from

const std::vector<std::size_t>& graph.edges_from(std::size_t v);

It returns the indices of the edges from the vertex $v$.

Constraints

$0 \leq v < n$

Time Complexity

$O(1)$

edges_to

const std::vector<std::size_t>& graph.edges_to(std::size_t v);

It returns the indices of the edges to the vertex $v$.

Constraints

$0 \leq v < n$

Time Complexity

$O(1)$

build

void graph.build();

It decomposes the graph into strongly connected components.

Constraints

graph.build() has not been called ever.

Time Complexity

$O(n + m \log m)$ where $m$ is the number of edges

scc_id

std::size_t graph.scc_id(std::size_t v);

It returns the index of the strongly connected components which contains the vertex $v$.

Constraints

graph.build() has been called ever.
$0 \leq v < n$

Time Complexity

$O(1)$

sccs

const std::vector<std::vector<std::size_t>>& graph.sccs();

It returns the list of the “list of the vertices” that satisfies the following.

Each vertex is in exactly one “list of the vertices”.
Each “list of the vertices” corresponds to the vertex set of a strongly connected component. The order of the vertices in the list is undefined.
The list of “list of the vertices” are sorted in topological order, i.e., for two vertices $u, v$ in different strongly connected components, if there is a directed path from $u$ to $v$, the list contains $u$ appears earlier than the list contains $v$.

Constraints

graph.build() has been called ever.

Time Complexity

$O(1)$

edges_in_scc

const std::vector<std::size_t>& graph.edges_in_scc(std::size_t x);

Let $E$ be the edges whose source is a vertex in the $x$-th strongly connected component and destination is a vertex in the $x$-th strongly connected component. It returns $E$.

Constraints

graph.build() has been called ever.
$0 \leq x < $ graph.sccs().size()

Time Complexity

$O(1)$

edges_from_scc

const std::vector<std::pair<std::size_t, std::vector<std::size_t>>>& graph.edges_from_scc(std::size_t x);

Let $E$ be the edges whose source is a vertex in the $x$-th strongly connected component and destination is a vertex not in the $x$-th strongly connected component. It groups $E$ by the strongly connected component which contains the destination, and returns the list of the groups.

Constraints

graph.build() has been called ever.
$0 \leq x < $ graph.sccs().size()

Time Complexity

$O(1)$

edges_to_scc

const std::vector<std::pair<std::size_t, std::vector<std::size_t>>>& graph.edges_to_scc(std::size_t x);

Let $E$ be the edges whose source is a vertex not in the $x$-th strongly connected component and destination is a vertex in the $x$-th strongly connected component. It groups $E$ by the strongly connected component which contains the source, and returns the list of the groups.

Constraints

graph.build() has been called ever.
$0 \leq x < $ graph.sccs().size()

Time Complexity

$O(1)$

Depends on

std::less by key (tools/less_by.hpp)

Verified with

Code

#ifndef TOOLS_SCC_GRAPH_HPP
#define TOOLS_SCC_GRAPH_HPP

#include <vector>
#include <utility>
#include <cstddef>
#include <cassert>
#include <stack>
#include <algorithm>
#include "tools/less_by.hpp"

namespace tools {
  class scc_graph {
  private:
    ::std::vector<::std::pair<::std::size_t, ::std::size_t>> m_edges;
    ::std::vector<::std::vector<::std::size_t>> m_graph;
    ::std::vector<::std::vector<::std::size_t>> m_rev_graph;
    ::std::vector<::std::size_t> m_vid2scc;
    ::std::vector<::std::vector<::std::size_t>> m_sccs;
    ::std::vector<::std::vector<::std::size_t>> m_edges_in_scc;
    ::std::vector<::std::vector<::std::pair<::std::size_t, ::std::vector<::std::size_t>>>> m_scc_graph;
    ::std::vector<::std::vector<::std::pair<::std::size_t, ::std::vector<::std::size_t>>>> m_rev_scc_graph;
    bool m_built;

  public:
    scc_graph() = default;
    scc_graph(const ::tools::scc_graph&) = default;
    scc_graph(::tools::scc_graph&&) = default;
    ~scc_graph() = default;
    ::tools::scc_graph& operator=(const ::tools::scc_graph&) = default;
    ::tools::scc_graph& operator=(::tools::scc_graph&&) = default;

    explicit scc_graph(const ::std::size_t n) : m_graph(n), m_rev_graph(n), m_vid2scc(n), m_built(false) {
    }

    ::std::size_t size() const {
      return this->m_graph.size();
    }

    ::std::size_t add_edge(const ::std::size_t from, const ::std::size_t to) {
      assert(from < this->size());
      assert(to < this->size());
      assert(!this->m_built);
      const auto edge_id = this->m_edges.size();
      this->m_edges.emplace_back(from, to);
      this->m_graph[from].push_back(edge_id);
      this->m_rev_graph[to].push_back(edge_id);
      return edge_id;
    }

    ::std::pair<::std::size_t, ::std::size_t> edge(const ::std::size_t i) const {
      assert(i < this->m_edges.size());
      return this->m_edges[i];
    }
    const ::std::vector<::std::size_t>& edges_from(const ::std::size_t i) const {
      assert(i < this->size());
      return this->m_graph[i];
    }
    const ::std::vector<::std::size_t>& edges_to(const ::std::size_t i) const {
      assert(i < this->size());
      return this->m_rev_graph[i];
    }

    void build() {
      assert(!this->m_built);
      ::std::stack<::std::size_t> ordered_by_dfs;
      {
        ::std::vector<bool> visited(this->size(), false);
        ::std::stack<::std::pair<bool, ::std::size_t>> stack;
        for (::std::size_t i = this->size(); i --> 0;) {
          stack.emplace(true, i);
        }
        while (!stack.empty()) {
          const auto [pre, here] = stack.top();
          stack.pop();
          if (pre) {
            if (visited[here]) continue;
            visited[here] = true;
            stack.emplace(false, here);
            for (const auto e : this->m_graph[here]) {
              const auto next = this->m_edges[e].second;
              if (visited[next]) continue;
              stack.emplace(true, next);
            }
          } else {
            ordered_by_dfs.push(here);
          }
        }
      }

      {
        ::std::vector<bool> visited(this->size(), false);
        while (!ordered_by_dfs.empty()) {
          const auto root = ordered_by_dfs.top();
          ordered_by_dfs.pop();
          if (visited[root]) continue;

          const auto scc_id = this->m_sccs.size();
          this->m_sccs.emplace_back();
          this->m_edges_in_scc.emplace_back();
          this->m_scc_graph.emplace_back();
          this->m_rev_scc_graph.emplace_back();

          ::std::stack<::std::size_t> stack({root});
          while (!stack.empty()) {
            const auto here = stack.top();
            stack.pop();
            if (visited[here]) continue;
            visited[here] = true;

            this->m_vid2scc[here] = scc_id;
            this->m_sccs[scc_id].push_back(here);

            for (const auto e : this->m_rev_graph[here]) {
              const auto next = this->m_edges[e].first;
              if (visited[next]) continue;
              stack.push(next);
            }
          }

          ::std::vector<::std::size_t> buffer; 
          for (const auto v : this->m_sccs[scc_id]) {
            for (const auto e : this->m_rev_graph[v]) {
              const auto u = this->m_edges[e].first;
              if (this->m_vid2scc[u] == this->m_vid2scc[v]) {
                this->m_edges_in_scc[scc_id].push_back(e);
              } else {
                buffer.push_back(e);
              }
            }
          }

          ::std::sort(buffer.begin(), buffer.end(), tools::less_by([&](const auto e) { return this->m_vid2scc[this->m_edges[e].first]; }));
          for (::std::size_t l = 0, r = 0; l < buffer.size(); l = r) {
            const auto u_scc_id = this->m_vid2scc[this->m_edges[buffer[l]].first];
            this->m_rev_scc_graph[scc_id].emplace_back(u_scc_id, ::std::vector<::std::size_t>());
            for (; r < buffer.size() && this->m_vid2scc[this->m_edges[buffer[l]].first] == this->m_vid2scc[this->m_edges[buffer[r]].first]; ++r);
            for (::std::size_t i = l; i < r; ++i) {
              this->m_rev_scc_graph[scc_id].back().second.push_back(buffer[i]);
            }
          }
        }

        for (::std::size_t v_scc_id = 0; v_scc_id < this->m_sccs.size(); ++v_scc_id) {
          for (const auto& [u_scc_id, edge_ids] : this->m_rev_scc_graph[v_scc_id]) {
            this->m_scc_graph[u_scc_id].emplace_back(v_scc_id, edge_ids);
          }
        }
      }

      this->m_built = true;
    }

    ::std::size_t scc_id(const ::std::size_t i) const {
      assert(i < this->size());
      assert(this->m_built);
      return this->m_vid2scc[i];
    }
    const ::std::vector<::std::vector<::std::size_t>>& sccs() const {
      assert(this->m_built);
      return this->m_sccs;
    }
    const ::std::vector<::std::size_t>& edges_in_scc(const ::std::size_t i) const {
      assert(i < this->m_sccs.size());
      assert(this->m_built);
      return this->m_edges_in_scc[i];
    }
    const ::std::vector<::std::pair<::std::size_t, ::std::vector<::std::size_t>>>& edges_from_scc(const ::std::size_t i) const {
      assert(i < this->m_sccs.size());
      assert(this->m_built);
      return this->m_scc_graph[i];
    }
    const ::std::vector<::std::pair<::std::size_t, ::std::vector<::std::size_t>>>& edges_to_scc(const ::std::size_t i) const {
      assert(i < this->m_sccs.size());
      assert(this->m_built);
      return this->m_rev_scc_graph[i];
    }
  };
}

#endif

#line 1 "tools/scc_graph.hpp"



#include <vector>
#include <utility>
#include <cstddef>
#include <cassert>
#include <stack>
#include <algorithm>
#line 1 "tools/less_by.hpp"



namespace tools {

  template <class F>
  class less_by {
  private:
    F selector;

  public:
    less_by(const F& selector) : selector(selector) {
    }

    template <class T>
    bool operator()(const T& x, const T& y) const {
      return selector(x) < selector(y);
    }
  };
}


#line 11 "tools/scc_graph.hpp"

namespace tools {
  class scc_graph {
  private:
    ::std::vector<::std::pair<::std::size_t, ::std::size_t>> m_edges;
    ::std::vector<::std::vector<::std::size_t>> m_graph;
    ::std::vector<::std::vector<::std::size_t>> m_rev_graph;
    ::std::vector<::std::size_t> m_vid2scc;
    ::std::vector<::std::vector<::std::size_t>> m_sccs;
    ::std::vector<::std::vector<::std::size_t>> m_edges_in_scc;
    ::std::vector<::std::vector<::std::pair<::std::size_t, ::std::vector<::std::size_t>>>> m_scc_graph;
    ::std::vector<::std::vector<::std::pair<::std::size_t, ::std::vector<::std::size_t>>>> m_rev_scc_graph;
    bool m_built;

  public:
    scc_graph() = default;
    scc_graph(const ::tools::scc_graph&) = default;
    scc_graph(::tools::scc_graph&&) = default;
    ~scc_graph() = default;
    ::tools::scc_graph& operator=(const ::tools::scc_graph&) = default;
    ::tools::scc_graph& operator=(::tools::scc_graph&&) = default;

    explicit scc_graph(const ::std::size_t n) : m_graph(n), m_rev_graph(n), m_vid2scc(n), m_built(false) {
    }

    ::std::size_t size() const {
      return this->m_graph.size();
    }

    ::std::size_t add_edge(const ::std::size_t from, const ::std::size_t to) {
      assert(from < this->size());
      assert(to < this->size());
      assert(!this->m_built);
      const auto edge_id = this->m_edges.size();
      this->m_edges.emplace_back(from, to);
      this->m_graph[from].push_back(edge_id);
      this->m_rev_graph[to].push_back(edge_id);
      return edge_id;
    }

    ::std::pair<::std::size_t, ::std::size_t> edge(const ::std::size_t i) const {
      assert(i < this->m_edges.size());
      return this->m_edges[i];
    }
    const ::std::vector<::std::size_t>& edges_from(const ::std::size_t i) const {
      assert(i < this->size());
      return this->m_graph[i];
    }
    const ::std::vector<::std::size_t>& edges_to(const ::std::size_t i) const {
      assert(i < this->size());
      return this->m_rev_graph[i];
    }

    void build() {
      assert(!this->m_built);
      ::std::stack<::std::size_t> ordered_by_dfs;
      {
        ::std::vector<bool> visited(this->size(), false);
        ::std::stack<::std::pair<bool, ::std::size_t>> stack;
        for (::std::size_t i = this->size(); i --> 0;) {
          stack.emplace(true, i);
        }
        while (!stack.empty()) {
          const auto [pre, here] = stack.top();
          stack.pop();
          if (pre) {
            if (visited[here]) continue;
            visited[here] = true;
            stack.emplace(false, here);
            for (const auto e : this->m_graph[here]) {
              const auto next = this->m_edges[e].second;
              if (visited[next]) continue;
              stack.emplace(true, next);
            }
          } else {
            ordered_by_dfs.push(here);
          }
        }
      }

      {
        ::std::vector<bool> visited(this->size(), false);
        while (!ordered_by_dfs.empty()) {
          const auto root = ordered_by_dfs.top();
          ordered_by_dfs.pop();
          if (visited[root]) continue;

          const auto scc_id = this->m_sccs.size();
          this->m_sccs.emplace_back();
          this->m_edges_in_scc.emplace_back();
          this->m_scc_graph.emplace_back();
          this->m_rev_scc_graph.emplace_back();

          ::std::stack<::std::size_t> stack({root});
          while (!stack.empty()) {
            const auto here = stack.top();
            stack.pop();
            if (visited[here]) continue;
            visited[here] = true;

            this->m_vid2scc[here] = scc_id;
            this->m_sccs[scc_id].push_back(here);

            for (const auto e : this->m_rev_graph[here]) {
              const auto next = this->m_edges[e].first;
              if (visited[next]) continue;
              stack.push(next);
            }
          }

          ::std::vector<::std::size_t> buffer; 
          for (const auto v : this->m_sccs[scc_id]) {
            for (const auto e : this->m_rev_graph[v]) {
              const auto u = this->m_edges[e].first;
              if (this->m_vid2scc[u] == this->m_vid2scc[v]) {
                this->m_edges_in_scc[scc_id].push_back(e);
              } else {
                buffer.push_back(e);
              }
            }
          }

          ::std::sort(buffer.begin(), buffer.end(), tools::less_by([&](const auto e) { return this->m_vid2scc[this->m_edges[e].first]; }));
          for (::std::size_t l = 0, r = 0; l < buffer.size(); l = r) {
            const auto u_scc_id = this->m_vid2scc[this->m_edges[buffer[l]].first];
            this->m_rev_scc_graph[scc_id].emplace_back(u_scc_id, ::std::vector<::std::size_t>());
            for (; r < buffer.size() && this->m_vid2scc[this->m_edges[buffer[l]].first] == this->m_vid2scc[this->m_edges[buffer[r]].first]; ++r);
            for (::std::size_t i = l; i < r; ++i) {
              this->m_rev_scc_graph[scc_id].back().second.push_back(buffer[i]);
            }
          }
        }

        for (::std::size_t v_scc_id = 0; v_scc_id < this->m_sccs.size(); ++v_scc_id) {
          for (const auto& [u_scc_id, edge_ids] : this->m_rev_scc_graph[v_scc_id]) {
            this->m_scc_graph[u_scc_id].emplace_back(v_scc_id, edge_ids);
          }
        }
      }

      this->m_built = true;
    }

    ::std::size_t scc_id(const ::std::size_t i) const {
      assert(i < this->size());
      assert(this->m_built);
      return this->m_vid2scc[i];
    }
    const ::std::vector<::std::vector<::std::size_t>>& sccs() const {
      assert(this->m_built);
      return this->m_sccs;
    }
    const ::std::vector<::std::size_t>& edges_in_scc(const ::std::size_t i) const {
      assert(i < this->m_sccs.size());
      assert(this->m_built);
      return this->m_edges_in_scc[i];
    }
    const ::std::vector<::std::pair<::std::size_t, ::std::vector<::std::size_t>>>& edges_from_scc(const ::std::size_t i) const {
      assert(i < this->m_sccs.size());
      assert(this->m_built);
      return this->m_scc_graph[i];
    }
    const ::std::vector<::std::pair<::std::size_t, ::std::vector<::std::size_t>>>& edges_to_scc(const ::std::size_t i) const {
      assert(i < this->m_sccs.size());
      assert(this->m_built);
      return this->m_rev_scc_graph[i];
    }
  };
}