这是我基础图论知识的一块漏洞,现在补上~~
先来看割点的定义:
对于无向图
,如果删除某个点
后,连通分量数目增加,则称点
是图
的割点。
怎样求出一个图所有的割点呢?不难想到一个的做法,但这显然不是最优的,考虑其他思路。
我们考虑一个无向图的DFS树,发现无向图中的边只可能是树边或是由子孙连向祖先的反向边。画个图更清楚:
上图是一个无向图,我们画出它的DFS树:
我们想一想,割点可能会具有怎样的性质?为了方便描述,我们把在某点的子树中(不包括
)的点集记为
,把不在
的子树中的点集记作
。观察上图中的点2,如果我们将它删除,那
中的4和
依然连通,删除2对它没有影响;但是
中的5和
由于2的消失变得不连通,图的连通分量个数增加,因此点2是该图的一个割点。
分析一下思路,我们可以得到这样一个结论:
对于某点
,若
中存在至少一点
,满足
与
之间没有任何边,则
是割点。
具体实现上,我们可以记录DFS过程中结点第一次访问的时间,以及结点及其后代所能连回的最早的祖先的
值
。于是问题转化成求某一结点是否存在一个儿子
使得
。解决这个问题,我们只需DFS全图一次即可,总复杂度
。
再来研究一下桥,先来看定义:
对于无向图
,如果删除某条边
后,连通分量数目增加,则称边
是图
的桥。
判断割点和桥大致过程是一样的,都是基于DFS的思想。不同之处在于,由于删除的是一条边,所以结论需要稍微改动:
对于某树边
,设
是
的父亲,若
中存在至少一点
,满足
与
除
外没有任何边,则
是桥。对于所有非树边
,一定不是桥。
转化一下条件,就是对于某一结点,求它的每个儿子
是否有
,如果是,则
是桥。求桥和求割点复杂度相同,同样是
。