同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1941_算法设计例题：强连通分量

2022-5-16 18:18| 发布者: Hocassian| 查看: 34| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504171300199-Problem List-采集的数据-后羿采集器.html

Pro.ID

1941

Title

算法设计例题：强连通分量

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1941

AC

Submit

383

Ratio

13.32%

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

给出一个有向图，求该图的强连通分量的个数。

输入

多测试用例，每个测试用例：

第一行给出这个图的顶点数n （ 1 ≤ n ≤ 1000 ）

第二行给出这个有向图的边数 e （ 0 ≤ n ≤ 100000 ）

第三行开始，共e行，每行两个正整数 a b，表示从顶点a发出一条弧到顶点b。

输出

Description

给出一个有向图，求该图的强连通分量的个数。

Input

多测试用例，每个测试用例：

第一行给出这个图的顶点数n （ 1 ≤ n ≤ 1000 ）

第二行给出这个有向图的边数 e （ 0 ≤ n ≤ 100000 ）

第三行开始，共e行，每行两个正整数 a b，表示从顶点a发出一条弧到顶点b。

Output

每个测试用例输出一行，一个正整数：该有向图的强连通分量的个数。

Sample Input

8
11
1 2
2 3
3 4
4 1
5 6
6 7
7 8
8 5
4 2
5 7
2 5

Sample Output

Hint

Sample的图如下：

Author

黄东鸿&John

样例输入