100 #P1147. D14*【强连通SCC】强连通模板[scy]

D14*【强连通SCC】强连通模板[scy]

【题目描述】

给出一个有向图有 nn 个点和 mm 条有向边,输出连通分量的数量。

概念:

  1. 什么是连通分量?

答:一个有向图中,选出某些点组成一个团体,这个团体中的任意两点都可互相到达。那么:选出来的这些点+这些点之间原有的边=叫做 连通分量。

  1. 只适合有向图

答:如果是无向图,那么并查集就可以解决了(还记得“家族”吗?)

附加1:什么是强连通图?

答:如果有向图 GG 的任意两个顶点都可以互相到达,称 GG 是一个强连通图。

附加2:什么是强连通分量?

答:比如 GG'GG 的最大的强连通子图,称为 GG 的强连通分量(可能不止一个,这个不重要)

比如输入样例1,有 33 个连通分量:(1)(1)(2,3,4,5,6)(2,3,4,5,6)(7)(7)

比如输入样例2,有 33 个连通分量:(1,2,3)(1,2,3)(4,6,7)(4,6,7)(5)(5)

【输入格式】

第一行两个整数 n,mn,m1n20000,1m2×1051 \le n \le 20000,1 \le m \le 2 \times 10^5)。

下来 mm 行,每行两个整数x,yx,y,表示一条从点 xx 出发到点 yy 的有向边。

【输出格式】

一行一个整数,表示连通分量的个数。

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