【图论练习】easy

2014年12月20日1,5801

hzwer蒟蒻刚刚学了点图论,现在他面对一张有向图

他想问你:

1:最少选择多少个点,使得从这些点出发能遍历完整个图

2:最少添加多少条有向边,能使得整个图成为强连通图

 

输入格式

第一行n,m,n个点m条边

接下来m行,每行u,v

表示一条u到v的有向边

输出格式

两行,分别为两问答案

 

样例输入

5 3

1 2

2 3

3 4

样例输出

2

2

 

数据范围

20%的数据N<=20, M<=50

40%的数据N<=2000,M<=20000

70%的数据N<=5000,M<=50000

100%的数据N<=10000,M<=50000

题解

第一问显然是入度为0的连通块个数

第二问,max{入度为0的连通块个数,出度为0的连通块个数}

特判连通块为1的情况

TAT第二问我想不出严格的证明,求神犇解答

大概是每个连通块,出度0的点,向其它连通块连边,使得形成一个环,其它的随便出度0连入度0?

唉反正我找不出反例暂且认为是正确的吧