acl_cpp.scc

scc.scc_graph

# scc_graph
from acl_cpp.scc import scc_graph

Decomposes a directed graph into strongly connected components.

Constructor

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

Creates a graph with \(n\) vertices and \(0\) edges.

Constraints

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

Complexity

\(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

Adds an edge from vertex \(\mathit{from\_}\) to vertex \(\mathit{to}\).

Constraints

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

Complexity

Amortized \(O(1)\)

scc_graph.scc

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

Returns a list of lists of vertices that satisfy the following conditions:

Each vertex appears in exactly one of the lists.
Each inner list corresponds to a strongly connected component. The order of vertices within each list is undefined.
The lists are topologically sorted. i.e., for vertices \(u\) and \(v\) in different strongly connected components, if there exists a directed path from \(u\) to \(v\), the list containing \(u\) appears earlier the list containing \(v\).

Complexity

Let \(m\) be the number of edges added, then

\(O(n + m)\)

Examples

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)