Strongly Connected Components

AC一覧

Problem Statement
問題文

Given a directed graph with $N$ vertices and $M$ edges. $i$-th edge is $(a_i, b_i)$. This graph may not be simple.

Please decompose this graph into SCCs and print them in topological order.

$N$ 頂点 $M$ 辺の有向グラフが与えられる。$i$ 番目の辺は $(a_i, b_i)$ である。このグラフは単純とは限らない。 このグラフを強連結成分分解し、トポロジカルソートして出力してください。

Constraints
制約

Input
入力

$N$ $M$
$a_0$ $b_0$
$a_1$ $b_1$
:
$a_{M - 1}$ $b_{M - 1}$

Output
出力

First line, print the number of SCCs $K$. Following $K$ line, we print the information of SCC for each line as follows. $l$ is the number of vertices of SCC, and $v_i$ is the vertex index.

$K$ を強連結成分の行数として、$1 + K$ 行出力する。 最初の行には $K$ を出力し、その後 $K$ 行では以下のように出力する。$l$ は強連結成分の頂点数であり、$v_i$ はその頂点番号である。

$l$ $v_0$ $v_1$ ... $v_{l-1}$

For each edge $(a_i, b_i)$, the line that contains $b_i$ can not be earlier than the line that contains $a_i$.

If there is a multiple solution, print any of them.

ここで、各辺 $(a_i, b_i)$ について、$b_i$ が $a_i$ より 先の行 に出現してはならない。

なお、正しい出力が複数存在する場合は、どれを出力しても構わない

Sample
サンプル

# 1

6 7
1 4
5 2
3 0
5 5
4 1
0 3
4 2
4
1 5
2 4 1
1 2
2 3 0

Forum


Timelimit: 5 secs

Before submitting, please confirm terms and conditions