前面这篇文章着重介绍了 Tarjan 算法找强连通分量的方法。
此文章着重介绍缩点。寻找 SCC 的方法依然是 Tarjan 算法。
缩点
温习一下缩点的定义:把强连通分量看成是一个大点,保留那些不在强连通分量里的边,这样的图就是缩点后的图。
看图就明白,缩点后的图要保留所有不在分量里的边,而且缩点后的图是一个有向无环图(DAG),也就是说可以进行拓扑排序。
还是拿上一篇文章的例子来说,缩点后的图长这样
跑一遍这样的代码,把在同一个 SCC 里的点染成同色。
运行以上代码后,3 个 SCC 的编号为
存储缩点后的图
接下来进入正题:如何储存缩点后的图?
在一般的图论题中,我们在读入数据时不会储存输入的数据,但这次不一样,我们需要储存输入的数据,以便再次利用这些点的关系。
所以使用数组存输入的数据就好。
在建立邻接表储存缩点后的图时,判断这些输入的点是否在同一个 SCC 中,如果不在就连边。
代码
其中 from
和 to
是用来储存输入数据的数组。
如果不需要原来的图,可以用 memset
函数初始化邻接表和 head
数组
(以前天真地认为结构体不能用 memset
进行初始化,后来才发现可以)
关于缩点这道模板题
洛谷上的模板题虽然叫缩点,但还需要找出一条路径使点权值和最大。
因为 SCC 中点可以互相到达,所以需要缩点使图变成一个有向无环图(DAG),SCC 内所有点权和即为缩点后该点的点权。
可以考虑用记忆化搜索(但是我太蒟蒻了不会记忆化搜索)。
还可以使用一些其(qi)他(yin)方(ji)法(qiao)。
通过魔改 SPFA 等最短路算法,把它修改成求点权最长路的算法(本质上就是把松弛变成扩张,把边权变成点权)。
初始化时要把自身所在点点权加上(不要初始化为 0),dis
数组要初始化为一个极小值。
把原来的判断 dis[v] > dis[u] + edge[i].cost
,魔改成 dis[v] < dis[u] + siz[v]
,其中 siz
数组存储了缩点后的点权。
这样跑一遍魔改后的 SPFA(LPFA),dis
数组中最大的数即为从源点出发点权和最大的路径上的点权和(说得有点绕)。
为了找到最优解,需要把每个点作为源点跑一遍魔改版 SPFA,像这样找出全局的最大值,这个值即为所求。
代码
Tarjan 求割点
割点:无向连通图中,删除掉某点及其所连边使整幅图不连通。
和 Tarjan 求 SCC 差不多,进行搜索时要传两个参,一个是自身,一个是祖先。
如果自身是树根,且有两个或以上的子树,那么它自身一定是割点。(去掉后两个子树不连通)
如果自身不是树根,但其儿子的 low 值大于这个点的 dfn 值,那么它也一定是割点。(子树中没有能够直接到达祖先的点)
代码