构造强连通图

如题所述

第1个回答  2022-07-05

将有向图变为强连通图
①连通图

找出所有的强连通分量, 然后缩成一个点,然后统计缩点之后的新图的出度为0的点的个数(记为cntOut),和入度为0的点的个数(记为cntIn)

那么要加边的条数就是max(cntOut,cntIn)

这个为什么呢?? 因为,如果一个点的入度为0,那么说明这个点是不可达的,如果一个点的出度为0,那么说明这个点到其它点是不可达的。

为了解决这个情况,那么只要在出度为0的点(设为u)和入度为0的点之间连一条u-->v的边,那么就解决了这种情况。

不断的连边,只要一个点问题没解决就要连边, 所以是在两者之间取max

注意,如果图本来就是强连通图,那么会缩成一个点,它出入度都为0,即max(cntOut,cntIn)=1,但本来不需要连任何边,所以ans=0,ans!=max(cntOut,cntIn),这个要特判

②非连通图

对于每个连通的分支之间,按照上面的方法变成强连通分量。

至于两个连通分量之间,连一条你指向我的边,再连一条我指向你的边就行了。

I - Proving Equivalences