Problems Submissions
Register Login 質問(Gitter) GitHub

Strongly Connected Components

AC一覧

問題文

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

制約

入力

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

出力

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

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

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

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

サンプル

# 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