Module: 强连通分量和图凝聚

Problem

1 /1

<分区> 给定一个有 N 个顶点和 M 个边的有向图 (1<=N<=20000, 1<=M<=200000)。找到给定图的强连通分量并对其凝聚进行拓扑排序。

<分区>

<分区> 输入

<分区> 该图在输入文件中给出如下：第一行包含数字 N 和 M。接下来的 M 行中的每一行都包含边的描述——从 1 到 N 的两个整数——边缘开始和结束编号。

<分区>

<分区> 输出

<分区> 在第一行打印数字 K ——给定图中强连通分量的数量。在下一行打印 N 个数字——对于每个顶点，打印该顶点所属的强连通分量的数量。强连通分量的编号方式必须是对于任何边，其开头的强连通分量的数量不超过其末端的强连通分量的数量。

<正文>

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

输入	输出
<分区> 10 19 <分区> 14 <分区> 78 <分区> 5 10 <分区> 8 9 <分区> 96 <分区> 26 <分区> 6 2 <分区> 38 <分区> 9 2 <分区> 7 2 <分区> 97 <分区> 4 5 <分区> 36 <分区> 73 <分区> 6 7 <分区> 108 <分区> 10 1 <分区> 29 <分区> 27	<分区> 2 <分区> 1 2 2 1 1 2 2 2 2 1