【题目描述】
给出一个有向图有n个点和m条有向边,输出连通分量的数量。
概念:
1. 什么是连通分量?
答:一个有向图中,选出某些点组成一个团体,这个团体中的任意两点都可互相到达。那么:选出来的这些点+这些点之间原有的边=叫做 连通分量。
2. 只适合有向图
答:如果是无向图,那么并查集就可以解决了(还记得“家族”吗?)
附加1:什么是强连通图?
答:如果有向图G的任意两个顶点都可以互相到达,称G是一个强连通图。
附加2:什么是强连通分量?
答:比如GG是G的最大的强连通子图,称为G的强连通分量(可能不止一个,这个不重要)
比如输入样例1,有3个连通分量:(1)、(2,3,4,5,6)、(7)
比如输入样例2,有3个连通分量:(1,2,3)、(4,6,7)、(5)
【输入格式】
第一行n和m(1<=n<=20000,1<=m<=20 0000),表示有向图总共n个点,点的编号由1~n。m表示m条有向边。
下来m行,每行两个整数x和y,表示一条有向边从点x出发到点y。
【输出格式】
一行一个整数,表示连通分量的个数。
【样例1输入】
7 7
1 2
2 3
3 4
4 5
5 6
6 2
5 2
【样例1输出】
3
【样例2输入】
7 11
1 2
1 4
2 3
2 5
3 1
3 5
3 6
4 6
5 7
6 7
7 4
【样例2输出】
3