AC. 梦想

frank_c1

割点和桥

发布于2016年03月13日 | 暂无评论 | 1,254阅读 | 图论

这是我基础图论知识的一块漏洞,现在补上~~

先来看割点的定义:

对于无向图G,如果删除某个点u后,连通分量数目增加,则称点u是图G的割点。

怎样求出一个图所有的割点呢?不难想到一个O(n(n+m))的做法,但这显然不是最优的,考虑其他思路。

我们考虑一个无向图的DFS树,发现无向图中的边只可能是树边或是由子孙连向祖先的反向边。画个图更清楚:

上图是一个无向图,我们画出它的DFS树:

我们想一想,割点可能会具有怎样的性质?为了方便描述,我们把在某点a的子树中(不包括a)的点集记为S(a),把不在a的子树中的点集记作T(a)。观察上图中的点2,如果我们将它删除,那S(2)中的4和T(2)依然连通,删除2对它没有影响;但是S(2)中的5和T(2)由于2的消失变得不连通,图的连通分量个数增加,因此点2是该图的一个割点。

分析一下思路,我们可以得到这样一个结论:

对于某点u,若S(u)中存在至少一点v,满足vT(u)之间没有任何边,则u是割点。

具体实现上,我们可以记录DFS过程中结点第一次访问的时间pre[u],以及结点及其后代所能连回的最早的祖先的prelow[u]。于是问题转化成求某一结点是否存在一个儿子v使得low[v] \ge pre[u]。解决这个问题,我们只需DFS全图一次即可,总复杂度O(n+m)

再来研究一下桥,先来看定义:

对于无向图G,如果删除某条边(u,v)后,连通分量数目增加,则称边(u,v)是图G的桥。

判断割点和桥大致过程是一样的,都是基于DFS的思想。不同之处在于,由于删除的是一条边,所以结论需要稍微改动:

对于某树边(u,v),设uv的父亲,若S(v) \cup \{v\}中存在至少一点k,满足kT(u) \cup \{u\}(u,v)外没有任何边,则(u,v)是桥。对于所有非树边(u,v),一定不是桥。

转化一下条件,就是对于某一结点u,求它的每个儿子v是否有low[v]>pre[u],如果是,则(u,v)是桥。求桥和求割点复杂度相同,同样是O(n+m)