Edge biconnected

图的割点、桥与双连通分支小结

###基本知识

具体知识点请看byvoid大大的文章(传送门)。

对于这一部份主要就是以Tarjan算法为核心。

该算法是R.Tarjan发明的。对图深度优先搜索,定义DFS(u)为u在搜索树(以下简称为树)中被遍历到的次序号。定义Low(u)为u或u的子树中能通过非父子边追溯到的最早的节点,即DFS序号最小的节点。根据定义,则有:

1
2
3
4
5
6
Low(u)=Min
{
DFS(u)
DFS(v) /*(u,v)为后向边(返祖边) 等价于 DFS(v)<DFS(u)且v不为u的父亲节点*/
Low(v) /*(u,v)为树枝边(父子边)*/
}

一个顶点u是割点,当且仅当满足(1)或(2)

(1) u为树根,且u有多于一个子树。

(2) u不为树根,且满足存在(u,v)为树枝边(或称父子边,即u为v在搜索树中的父亲),使得DFS(u)<=Low(v)。

一条无向边(u,v)是桥,当且仅当(u,v)为树枝边,且满足DFS(u)<Low(v)。

###题目

####Lightoj 1026

求割边

####Lightoj 1063

求割点

####Lightoj 1291

构建边双连通分量