POJ1236Network of Schools(强连通分量 + 缩点)

题目链接Network of Schools

参考斌神博客

强连通分量缩点求入度为0的个数和出度为0的分量个数

题目大意:N(2<N<100)各学校之间有单向的网络,每个学校得到一套软件后,可以通过单向网络向周边的学校传输,问题1:初始至少需要向多少个学校发放软件,使得网络内所有的学校最终都能得到软件。2,至少需要添加几条传输线路(边),使任意向一个学校发放软件后,经过若干次传送,网络内所有的学校最终都能得到软件。

 

也就是:

—        给定一个有向图,求:

 

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

 

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

 

—        顶点数<= 100

解题思路:

—        1. 求出所有强连通分量

—        2. 每个强连通分量缩成一点,则形成一个有向无环图DAG

—        3. DAG上面有多少个入度为0的顶点,问题1的答案就是多少

原文地址:https://www.cnblogs.com/zhaopAC/p/5361699.html