← 返回题目列表

AtCoder · practice2_g

G. 强连通分量

中文机器翻译题面 查看原题

分数: 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