SCC
有向グラフを強連結成分分解します。
コンストラクタ
scc_graph graph(int n)
$n$ 頂点 $0$ 辺の有向グラフを作る。
制約
計算量
add_edge
void graph.add_edge(int from, int to)
頂点 from から頂点 to へ有向辺を足す。
制約
- $0 \leq \mathrm{from} \lt n$
- $0 \leq \mathrm{to} \lt n$
計算量
scc
vector<vector<int>> graph.scc()
以下の条件を満たすような、「頂点のリスト」のリストを返します。
- 全ての頂点がちょうど1つずつ、どれかのリストに含まれます。
- 内側のリストと強連結成分が一対一に対応します。リスト内での頂点の順序は未定義です。
- リストはトポロジカルソートされています。異なる強連結成分の頂点 $u, v$ について、$u$ から $v$ に到達できる時、$u$ の属するリストは $v$ の属するリストよりも前です。
計算量
追加した辺の本数を $m$ として
使用例
#include <atcoder/scc>
#include <cstdio>
using namespace std;
using namespace atcoder;
int main() {
int n, m;
scanf("%d %d", &n, &m);
scc_graph g(n);
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
g.add_edge(u, v);
}
auto scc = g.scc();
printf("%d\n", int(scc.size()));
for (auto v : scc) {
printf("%d", int(v.size()));
for (int x : v) {
printf(" %d", x);
}
printf("\n");
}
return 0;
}