1. 题目

传送门= ̄ω ̄=

2. 题解

强联通分量,缩点模板题。
第一个问题的答案是缩点以后入度为0的点的个数
第二个问题的答案是缩点以后入度为0的点的个数和出度为0的点的个数中较大的那个
如果只有1个强联通分量,那么第二问答案为0,需要特判

至于证明的话,可以看这个,我懒得写了:

—给定一个有向图,求:

1) 至少要选几个顶点,才能做到从这些顶点出发,可以到达全部顶点

2) 至少要加多少条边,才能使得从任何一个顶点出发,都能到达全部顶点

— 顶点数<= 100 解题思路: 1. 求出所有强连通分量 2. 每个强连通分量缩成一点,则形成一个有向无环图DAG。 3. DAG上面有多少个入度为0的顶点,问题1的答案就是多少 在DAG上要加几条边,才能使得DAG变成强连通的,问题2的答案就是多少 加边的方法: 要为每个入度为0的点添加入边,为每个出度为0的点添加出边 假定有 n 个入度为0的点,m个出度为0的点,如何加边? 把所有入度为0的点编号 0,1,2,3,4 ….N -1 每次为一个编号为i的入度0点可达的出度0点,添加一条出边,连到编号为(i+1)%N 的那个出度0点, 这需要加n条边 若 m <= n,则 加了这n条边后,已经没有入度0点,则问题解决,一共加了n条边 若 m > n,则还有m-n个入度0点,则从这些点以外任取一点,和这些点都连上边,即可,这还需加m-n条边。
所以,max(m,n)就是第二个问题的解
此外:当只有一个强连通分支的时候,就是缩点后只有一个点,虽然入度出度为0的都有一个,但是实际上不需要增加清单的项了,所以答案是1,0;

代码(kosaraju):