点双连通分量和割顶和桥
对于无向图G，如果删除某个点u后，连通分量数目增加，称u为图的关节点（articulation vertex）或割顶（cut vertex）。对于联通图，割顶就是删除之后使图不再联通的点。
至于如何求割顶。
膜拜Tarjan大爷。
我们访问每一个点。在DFS森林中的边称为树边，第一次处理时从后代指向祖先的边称为反向边。然而在无向图中，除了树边，其他边都是反向边（有向图还有正向边和横叉边）。
对于无向图。我们讨论一个点是不是割顶，需要分两种情况：
- 这个点是DFS树的根节点，那么它是割顶，就需要它有两个或以上数目的儿子。
- 这个点不是DFS树的根节点，那么它没有【有可以到达它的祖先的反向边的子孙】。
所以就需要low值来判断（low值是它通过边或者它的子孙所能到达的节点的dfn值中中最小的dfn值）。
实际操作中，我们也是分两种情况讨论的：
- 它是根节点，那么就数一数它的儿子个数。
- 它不是根节点，如果它的low值不小于dfn值，并且它的父亲不是根节点，那么它的父亲就是割顶。（并不是直接判断它，而是通过儿子判断父亲。别问我为什么这样，我备用交换机抄的lrd的模板。）
然后我们就求出了割顶。
讨论我们这个题目[矿场搭建]：
求出所有的割顶之后，整个图被分成了几个联通块。我们对每个联通块含有的割顶数目进行讨论：
- 如果块里没有割顶，就建两个口，一个坏掉之后可以跑另一个。
- 如果块里只有一个割顶，那么就建一个口，这个口坏了就从割顶跑出去，割顶或者别的地方坏了就从这个口跑出去。
- 如果块里有两个或以上割顶，就一个也不建，如果一个点坏了就从割顶跑出去，一个割顶坏了就从别的割顶跑出去。
所以我们这时就有了两种办法：
- 求出割顶，然后对不是割顶的点进行dfs，能够求出一个块，然后统计这个块连接着多少割顶，如上讨论。
- 求割顶顺路求出BCC，然后对于每个BCC进行分类讨论（至于无向图的BCC，只要SCC的代码略加标记即可。https://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之间存在重边的话，就不是桥了，所以我们要对重边判定.
评论