分数: 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}
输出
打印 1+K 行,其中 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