/ Vijos / 题库 /

强连通分量

强连通分量

时间限制:1秒  内存限制:256M


【题目描述】

  有一个 \(n\) 个点,\(m\) 条边的有向图,请求出这个图点数大于 \(1\) 的强连通分量个数。

【输入格式】

  第一行为两个整数 \(n\) 和 \(m\)。
  第二行至 \(m+1\) 行,每一行有两个整数 \(a\) 和 \(b\),表示有一条从 \(a\) 到 \(b\) 的有向边。

【输出格式】

  仅一行,表示点数大于 \(1\) 的强连通分量个数。

【输入输出样例1】

 Input

5 4
2 4
3 5
1 2
4 1

 Output

1

【测试点性质】

  对于全部的测试点,保证 \(2\le n \le 10^4\),\(2\le m\le 5\times 10^4\),\(1 \leq a, b \leq n\)。

【来源】

  Mr.he

信息

ID
3237
难度
9
分类
图结构 | 强连通分量 点击显示
标签
(无)
递交数
4
已通过
1
通过率
25%
被复制
2
上传者