comp-library

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

View the Project on GitHub luzhiled1333/comp-library

:heavy_check_mark: 強連結成分分解(Decomposition of Strongly Connected Components, SCC)
(src/graph/decomposition/strongly-connected-components.hpp)

Appendix

テンプレートパラメータに渡すグラフ $G$ の仕様について

コンストラクタ

decomposition::StronglyConnectedComponents(const G &g)

有向グラフ g を強連結成分分解する。

計算量

groups

std::vector< std::vector< usize > > groups() const

$K$ を強連結成分の個数として、強連結成分の頂点のリストのリスト $L=(L_0, L_1, \cdots, L_K)$ を返す。

$L$ はトポロジカルソートされている。すなわち、g の各辺 $(u_i, v_i)$ について、頂点 $v_i$ を含む強連結成分が頂点 $u_i$ を含む強連結成分より前に出現しない。

group_ids

std::vector< usize > group_ids() const

それぞれの頂点に対応する強連結成分の番号を格納したリストを返す。

Depends on

Verified with

Code

#pragma once

#include "src/cpp-template/header/change-min.hpp"
#include "src/cpp-template/header/rep.hpp"
#include "src/cpp-template/header/size-alias.hpp"

#include <vector>

namespace luz::decomposition {

  template < class G >
  class StronglyConnectedComponents {
    using graph     = G;
    using cost_type = typename graph::cost_type;

    graph g;
    usize g_size;
    std::vector< usize > low, ord, visited, group_id;
    usize ord_cnt, group_cnt;

    void dfs(usize v) {
      low[v] = ord[v] = ord_cnt++;
      visited.emplace_back(v);
      for (auto& e: g[v]) {
        if (ord[e.to] == g_size) {
          dfs(e.to);
          chmin(low[v], low[e.to]);
        } else {
          chmin(low[v], ord[e.to]);
        }
      }
      if (low[v] == ord[v]) {
        while (true) {
          usize u = visited.back();
          visited.pop_back();
          ord[u]      = g_size + 1;
          group_id[u] = group_cnt;
          if (u == v) break;
        }
        group_cnt++;
      }
    }

   public:
    explicit StronglyConnectedComponents(const graph& g_)
        : g(g_),
          g_size(g.size()),
          low(g_size),
          ord(g_size, g_size),
          group_id(g_size),
          ord_cnt(0),
          group_cnt(0) {
      visited.reserve(g_size);
      for (usize v: rep(0, g_size)) {
        if (ord[v] == g_size) {
          dfs(v);
        }
      }
      for (auto& id: group_id) {
        id = group_cnt - id - 1;
      }
    }

    std::vector< std::vector< usize > > groups() const {
      std::vector< usize > counts(group_cnt);
      for (usize i: rep(0, g_size)) {
        counts[group_id[i]]++;
      }
      std::vector< std::vector< usize > > groups(group_cnt);
      for (usize i: rep(0, group_cnt)) {
        groups[i].reserve(counts[i]);
      }
      for (usize i: rep(0, g_size)) {
        groups[group_id[i]].emplace_back(i);
      }
      return groups;
    }

    std::vector< usize > group_ids() const {
      return group_id;
    }
  };

} // namespace luz::decomposition
#line 2 "src/graph/decomposition/strongly-connected-components.hpp"

#line 2 "src/cpp-template/header/change-min.hpp"

namespace luz {

  template < typename T1, typename T2 >
  inline bool chmin(T1 &a, T2 b) {
    return a > b and (a = b, true);
  }

} // namespace luz
#line 2 "src/cpp-template/header/rep.hpp"

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

} // namespace luz
#line 4 "src/cpp-template/header/rep.hpp"

#include <algorithm>

namespace luz {

  struct rep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        ++i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rep(const usize f, const usize l) noexcept
        : f(std::min(f, l)),
          l(l) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

  struct rrep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        --i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rrep(const usize f, const usize l) noexcept
        : f(l - 1),
          l(std::min(f, l) - 1) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

} // namespace luz
#line 6 "src/graph/decomposition/strongly-connected-components.hpp"

#include <vector>

namespace luz::decomposition {

  template < class G >
  class StronglyConnectedComponents {
    using graph     = G;
    using cost_type = typename graph::cost_type;

    graph g;
    usize g_size;
    std::vector< usize > low, ord, visited, group_id;
    usize ord_cnt, group_cnt;

    void dfs(usize v) {
      low[v] = ord[v] = ord_cnt++;
      visited.emplace_back(v);
      for (auto& e: g[v]) {
        if (ord[e.to] == g_size) {
          dfs(e.to);
          chmin(low[v], low[e.to]);
        } else {
          chmin(low[v], ord[e.to]);
        }
      }
      if (low[v] == ord[v]) {
        while (true) {
          usize u = visited.back();
          visited.pop_back();
          ord[u]      = g_size + 1;
          group_id[u] = group_cnt;
          if (u == v) break;
        }
        group_cnt++;
      }
    }

   public:
    explicit StronglyConnectedComponents(const graph& g_)
        : g(g_),
          g_size(g.size()),
          low(g_size),
          ord(g_size, g_size),
          group_id(g_size),
          ord_cnt(0),
          group_cnt(0) {
      visited.reserve(g_size);
      for (usize v: rep(0, g_size)) {
        if (ord[v] == g_size) {
          dfs(v);
        }
      }
      for (auto& id: group_id) {
        id = group_cnt - id - 1;
      }
    }

    std::vector< std::vector< usize > > groups() const {
      std::vector< usize > counts(group_cnt);
      for (usize i: rep(0, g_size)) {
        counts[group_id[i]]++;
      }
      std::vector< std::vector< usize > > groups(group_cnt);
      for (usize i: rep(0, group_cnt)) {
        groups[i].reserve(counts[i]);
      }
      for (usize i: rep(0, g_size)) {
        groups[group_id[i]].emplace_back(i);
      }
      return groups;
    }

    std::vector< usize > group_ids() const {
      return group_id;
    }
  };

} // namespace luz::decomposition
Back to top page