题目链接
解题方法:强连通分量
题目分析
题目大意
给出一个n
个点,m
条边的有向图,问在图中最少要加多少条边能使得该图变成一个强连通图
解析
为了使图成为强连通图,那么我们就要消灭所有入度和出度为0
的点。
遍历每一条边,不妨设其是u指向v,那么u所在的强连通分量就有出度,v所在的强连通分量就有入度,我们统计出有多少个强连通分量的有出度,多少个强连通分量有入度,然后取两者的较大者即可,当图是一个强连通分量图时,也就是说图中没有需要加边的点,那么我们就输出0
,否则,我们取max(入度为0的点的个数,出度为0的点的个数)即可。
代码
1 |
|