Strongly-Connected Components ( 強連結成分 )

C++ 用ライブラリ一覧に戻る

ソースコード

nachia/graph/strongly-connected-components.hpp

主な機能

有向グラフを強連結成分に分解する。強連結成分を縮約すると DAG が得られるが、そのトポロジカル順序を $1$ つとって強連結成分に番号を振る。

$2$ 頂点 $s$ , $t$ 間が強連結であるとは、 $s$ から $t$ のパスと $t$ から $s$ のパスが両方存在することである。この $s$ , $t$ の関係は推移律を満たすので、その同値類（頂点集合）をとり、その誘導部分グラフを強連結成分と呼ぶ。

頂点 $v$ が属する強連結成分に振られた番号を $I(v)$ とする。強連結成分に含まれない辺 $s\rightarrow t$ について $I(s)\lt I(t)$ が成り立つようにする。

ケースによっては（特に大きいサイクル $1$ 個のケース） AtCoder Library の internal の scc よりも高速かつ省メモリである。

再帰の深い関数を使わない。

struct SCC

コンストラクタ

StronglyConnectedComponents();
StronglyConnectedComponents(Graph G);

nachia::Graph とは？

• 頂点数： $0 \leq n \leq 2 \times 10^7$
• 辺数： $0 \leq m \leq 2 \times 10^7$
• $G$ は有向グラフ。
• $O(n + m)$ 時間

メインの計算を行う。引数がない場合は空グラフに対して処理する。

numComponents

int numComponents() const noexcept;

強連結成分の個数を返す。

getCsr

CsrArray<int> getCsr() const;

• $O(n + m)$ 時間

各強連結成分の頂点集合を返す。頂点の番号は与えられたグラフのものである。

getMapping

std::vector<int> getMapping() const;

長さ $n$ の配列を返す。各頂点が属する強連結成分の番号を表す。

参考

• コラム 非再帰DFS link

---

TOP PAGE