SCC (Strongly Connected Components)
(library/graph/scc.hpp)

• View this file on GitHub
• Last update: 2025-08-17 00:21:01+09:00
• Include: #include "library/graph/scc.hpp"

SCC (Strongly Connected Components)

強連結成分分解する。

• scc(T adj_list) -> vector<vector<size_t>>: 強連結成分分解を行い、「頂点のリスト」のリストを返す。トポロジカルソートされる。 $O(n + m)$

詳細

• Combinatorial Optimization p40

Depends on

• library/_internal/graph-base.hpp

Verified with

• tests/graph/scc/abc256-e.test.cpp
• tests/graph/scc/abc296-e.test.cpp
• tests/graph/scc/libchecker.test.cpp

Code

#pragma once

#include <cassert>
#include <functional>
#include <vector>
using namespace std;

#include "../_internal/graph-base.hpp"

namespace asalib::graph {
  template<_internal::adjacency_list T>
  vector<vector<size_t>> scc(const T& adj_list) {
    const size_t n_vertex = adj_list.size();
    vector adj_list_rev(n_vertex, vector<size_t>());
    for (size_t v = 0; v < n_vertex; ++v) {
      for (const size_t& u : adj_list[v]) {
        assert(u < n_vertex);
        adj_list_rev[u].emplace_back(v);
      }
    }

    constexpr size_t Unvisited = -1;
    vector visited(n_vertex, false);
    size_t order_num = 0;
    vector ord2pt(n_vertex, Unvisited);

    function<void(size_t)> visit1 = [&](size_t v) {
      visited[v] = true;
      for (const size_t& w : adj_list[v]) {
        if (!visited[w]) visit1(w);
      }
      ord2pt[order_num++] = v;
    };

    for (size_t v = 0; v < n_vertex; ++v) {
      if (!visited[v]) visit1(v);
    }

    visited.assign(n_vertex, false);
    size_t comp_num = 0;
    vector comp(n_vertex, Unvisited);

    function<void(size_t)> visit2 = [&](size_t v) {
      visited[v] = true;
      for (const size_t& w : adj_list_rev[v]) {
        if (!visited[w]) visit2(w);
      }
      comp[v] = comp_num;
    };

    for (int i = n_vertex - 1; i >= 0; --i) {
      if (!visited[ord2pt[i]]) visit2(ord2pt[i]), ++comp_num;
    }

    vector<vector<size_t>> res(comp_num);
    for (size_t v = 0; v < n_vertex; ++v) {
      res[comp[v]].emplace_back(v);
    }
    return res;
  }
}  // namespace asalib::graph

#line 2 "library/graph/scc.hpp"

#include <cassert>
#include <functional>
#include <vector>
using namespace std;

#line 2 "library/_internal/graph-base.hpp"

#include <concepts>
#include <cstddef>
#include <ranges>
#include <utility>
using namespace std;

namespace asalib::_internal {
  // vector<vector<int>> とかの隣接リストを表す型
  template<class T>
  concept adjacency_list = requires(T t) {
    { t.size() } -> convertible_to<size_t>;
    { t[0] } -> ranges::range;
    { *ranges::begin(t[0]) } -> convertible_to<size_t>;
  };

  // 辺のリストを表す型
  // 重み付きも考慮し pair<int, int> と tuple<int, int, int> の両方を許容
  template<class T>
  concept edge_list = requires(T t) {
    { t.size() } -> convertible_to<size_t>;
    { get<0>(t[0]) } -> convertible_to<size_t>;
    { get<1>(t[0]) } -> convertible_to<size_t>;
  };
}  // namespace asalib::_internal
#line 9 "library/graph/scc.hpp"

namespace asalib::graph {
  template<_internal::adjacency_list T>
  vector<vector<size_t>> scc(const T& adj_list) {
    const size_t n_vertex = adj_list.size();
    vector adj_list_rev(n_vertex, vector<size_t>());
    for (size_t v = 0; v < n_vertex; ++v) {
      for (const size_t& u : adj_list[v]) {
        assert(u < n_vertex);
        adj_list_rev[u].emplace_back(v);
      }
    }

    constexpr size_t Unvisited = -1;
    vector visited(n_vertex, false);
    size_t order_num = 0;
    vector ord2pt(n_vertex, Unvisited);

    function<void(size_t)> visit1 = [&](size_t v) {
      visited[v] = true;
      for (const size_t& w : adj_list[v]) {
        if (!visited[w]) visit1(w);
      }
      ord2pt[order_num++] = v;
    };

    for (size_t v = 0; v < n_vertex; ++v) {
      if (!visited[v]) visit1(v);
    }

    visited.assign(n_vertex, false);
    size_t comp_num = 0;
    vector comp(n_vertex, Unvisited);

    function<void(size_t)> visit2 = [&](size_t v) {
      visited[v] = true;
      for (const size_t& w : adj_list_rev[v]) {
        if (!visited[w]) visit2(w);
      }
      comp[v] = comp_num;
    };

    for (int i = n_vertex - 1; i >= 0; --i) {
      if (!visited[ord2pt[i]]) visit2(ord2pt[i]), ++comp_num;
    }

    vector<vector<size_t>> res(comp_num);
    for (size_t v = 0; v < n_vertex; ++v) {
      res[comp[v]].emplace_back(v);
    }
    return res;
  }
}  // namespace asalib::graph

Back to top page