/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
N 頂点 M 辺の有向グラフが与えられる。i 番目の辺は (a_i, b_i) である。このグラフは単純とは限らない。 このグラフを強連結成分分解し、トポロジカルソートして出力してください。
制約
- 1 \leq N \leq 500,000
- 1 \leq M \leq 500,000
- 0 \leq a_i, b_i < N
入力
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
出力例 1
4 1 5 2 4 1 1 2 2 3 0
Score : 100 points
Problem Statement
You are given a directed graph with N vertices and M edges, not necessarily simple. The i-th edge is oriented from the vertex a_i to the vertex b_i. Divide this graph into strongly connected components and print them in their topological order.
Constraints
- 1 \leq N \leq 500,000
- 1 \leq M \leq 500,000
- 0 \leq a_i, b_i < N
Input
Input is given from Standard Input in the following format:
N M
a_0 b_0
a_1 b_1
:
a_{M - 1} b_{M - 1}
Output
Print 1+K lines, where K is the number of strongly connected components. Print K on the first line. Print the information of each strongly connected component in next K lines in the following format, where l is the number of vertices in the strongly connected component and v_i is the index of the vertex in it.
l v_0 v_1 ... v_{l-1}
Here, for each edge (a_i, b_i), b_i should not appear in earlier line than a_i.
If there are multiple correct output, print any of them.
Sample Input 1
6 7 1 4 5 2 3 0 5 5 4 1 0 3 4 2
Sample Output 1
4 1 5 2 4 1 1 2 2 3 0