acl_cpp.scc

scc.scc_graph

# scc_graph
from acl_cpp.scc import scc_graph

有向グラフを強連結成分分解します。

コンストラクタ

# scc_graph::scc_graph(int n)
def scc_graph(n: int = 0) -> scc_graph

\(n\) 頂点 \(0\) 辺のグラフを作成します。

制約

\(0 \le n < 2^{31}\)

計算量

\(O(n)\)

scc_graph.add_edge

# void scc_graph::add_edge(int from, int to)
def scc_graph.add_edge(from_: int, to: int) -> None

頂点 \(\mathit{from\_}\) から頂点 \(\mathit{to}\) への辺を追加します。

制約

\(0 \le \mathit{from\_} < n\)
\(0 \le \mathit{to} < n\)

計算量

ならし \(O(1)\)

scc_graph.scc

# vector<vector<int>> scc_graph::scc()
def scc_graph.scc() -> list[list[int]]

以下の条件を満たすような、「頂点のリスト」のリストを返します。

全ての頂点がちょうど 1 つずつ、どれかのリストに含まれます。
内側のリストと強連結成分が一対一に対応します。リスト内での頂点の順序は未定義です。
リストはトポロジカルソートされています。異なる強連結成分の頂点 \(u, v\) について、\(u\) から \(v\) に到達できる時、\(u\) の属するリストは \(v\) の属するリストよりも前です。

計算量

追加した辺の本数を \(m\) として

\(O(n + m)\)

使用例

AC code of https://atcoder.jp/contests/practice2/tasks/practice2_g

from acl_cpp.scc import scc_graph

N, M = map(int, input().split())
g = scc_graph(N)

for _ in range(M):
    u, v = map(int, input().split())
    g.add_edge(u, v)

scc = g.scc()
print(len(scc))
for component in scc:
    print(len(component), *component)