最大半连通子图

问题叙述

https://www.luogu.org/problemnew/show/P2272

前置技能

[缩点][https://www.cnblogs.com/five20/p/7594239.html]

解决问题

大的想法

首先有一个大的想法,就是首先缩点,把图缩成一个有向无环图(之所以可以这样,是因为任何一个强连通分量是都是一个原图的半连通子图)。然后用拓扑排序进行动态规划,计算最长链的数量和最长链的大小。

Detail 1:关于缩点的问题。

问题:现在大家想想一个有向图,有1->2, 2->3, 3->4, 4->1, 5->2, 5->3, 5->4这些边。那么缩点的时候如果从1号点开始跑TARJAN,会发现根本搜不到5这个点。所以要进行好几次搜索。但这样的话,搜到5号点的时候low[5]=1, dfn[5]=5。这就表明5并不是一个强连通分量的首领。所以这样做就出现了问题。那该怎么办?

解决:在计算low的时候,low[i]并不是对于任何一个j都执行low[i] = min(low[i], low[j])的。在j已经确定是别的连通分量里面的点的时候,low[i]就不从low[j]更新了(否则的话就会在上述情况中出现问题)。

Read More