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

SCC(int n)

n 頂点 0 辺の有向グラフを作る。

計算量

$O(n)$

public void addEdge(int from, int to)

頂点 from から頂点 to へ有向辺を足す。

制約

• 0 <= from < n
• 0 <= to < n

計算量

amortized $O(1)$

public int[][] build()

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

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

計算量

追加した辺の本数を m として $O(n + m)$

public int id(int i)

頂点 i が (トポロジカル順序において) 何番目の強連結成分に属しているかを返します。即ち，build で得られる「頂点の配列」の配列を g とすると、g[id(i)][j] = i なる j が存在します。

ただし、build を呼ぶ前にこのメソッドが呼ばれた場合は、実行時例外 UnsupportedOperationException が発生します。

制約

• build メソッドを既に呼んでいる
• 0 <= i < n

計算量

$O(1)$

AtCoder Library Practice Contest G - SCC