最小AC爆零流

rp+=INF!(

点双连通分量和割顶和桥

ItalyLily:

对于无向图G,如果删除某个点u后,连通分量数目增加,称u为图的关节点(articulation vertex)或割顶(cut vertex)。对于联通图,割顶就是删除之后使图不再联通的点。


至于如何求割顶。


膜拜Tarjan大爷。


我们访问每一个点。在DFS森林中的边称为树边,第一次处理时从后代指向祖先的边称为反向边。然而在无向图中,除了树边,其他边都是反向边(有向图还有正向边和横叉边)。


对于无向图。我们讨论一个点是不是割顶,需要分两种情况:



  1. 这个点是DFS树的根节点,那么它是割顶,就需要它有两个或以上数目的儿子。

  2. 这个点不是DFS树的根节点,那么它没有【有可以到达它的祖先的反向边的子孙】。


所以就需要low值来判断(low值是它通过边或者它的子孙所能到达的节点的dfn值中中最小的dfn值)。


实际操作中,我们也是分两种情况讨论的:



  1. 它是根节点,那么就数一数它的儿子个数。

  2. 它不是根节点,如果它的low值不小于dfn值,并且它的父亲不是根节点,那么它的父亲就是割顶。(并不是直接判断它,而是通过儿子判断父亲。别问我为什么这样,我备用交换机抄的lrd的模板。)


然后我们就求出了割顶。


讨论我们这个题目[矿场搭建]:


求出所有的割顶之后,整个图被分成了几个联通块。我们对每个联通块含有的割顶数目进行讨论:



  1. 如果块里没有割顶,就建两个口,一个坏掉之后可以跑另一个。

  2. 如果块里只有一个割顶,那么就建一个口,这个口坏了就从割顶跑出去,割顶或者别的地方坏了就从这个口跑出去。

  3. 如果块里有两个或以上割顶,就一个也不建,如果一个点坏了就从割顶跑出去,一个割顶坏了就从别的割顶跑出去。


所以我们这时就有了两种办法:



  1. 求出割顶,然后对不是割顶的点进行dfs,能够求出一个块,然后统计这个块连接着多少割顶,如上讨论。

  2. 求割顶顺路求出BCC,然后对于每个BCC进行分类讨论(至于无向图的BCC,只要SCC的代码略加标记即可。http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1076是一道BCC的模板题)。


P.S.


以下是来自CSDN的桥的相关知识:

桥    定义:

     在一张无向图中,如果去掉边(u,v)使得图的连通分支数增加,那么边(u,v)便称为桥.


  tarjan算法求无向图的桥:


     边(u,v)是无向图的桥当且仅当(u,v)满足 low[v]>DFN[u]


   简单说明:


     这个式子的言外之意也就是边(u,v)是v到达其祖先的必经之路,所以去掉边(u,v),连通分支数就会增加,但是如果u,v之间存在重边的话,就不是桥了,所以我们要对重边判定.


 



评论

热度(10)

  1. 最小AC爆零流ItalyLily 转载了此文字