Problem1147--[视频]强连通(模版 元问题byscy)

1147: [视频]强连通(模版 元问题byscy)

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 7  Solved: 5
[Status] [Submit] [Creator:]

Description

【题目描述】
   给出一个有向图有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


Source/Category