D14*【强连通SCC】强连通模板[scy]
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
【题目描述】
给出一个有向图有 个点和 条有向边,输出连通分量的数量。
概念:
- 什么是连通分量?
答:一个有向图中,选出某些点组成一个团体,这个团体中的任意两点都可互相到达。那么:选出来的这些点+这些点之间原有的边=叫做 连通分量。
- 只适合有向图
答:如果是无向图,那么并查集就可以解决了(还记得“家族”吗?)
附加1:什么是强连通图?
答:如果有向图 的任意两个顶点都可以互相到达,称 是一个强连通图。
附加2:什么是强连通分量?
答:比如 是 的最大的强连通子图,称为 的强连通分量(可能不止一个,这个不重要)

比如输入样例1,有 个连通分量:、、
比如输入样例2,有 个连通分量:、、
【输入格式】
第一行两个整数 ()。
下来 行,每行两个整数,表示一条从点 出发到点 的有向边。
【输出格式】
一行一个整数,表示连通分量的个数。
7 7
1 2
2 3
3 4
4 5
5 6
6 2
5 2
3
7 11
1 2
1 4
2 3
2 5
3 1
3 5
3 6
4 6
5 7
6 7
7 4
3