双连通分量

定义

双连通分量又分点双连通分量和边双连通分量两种。

若一个无向图中的去掉任意一个节点（一条边）都不会改变此图的连通性，即不存在割点（桥），则称作点（边）双连通图。

一个无向图中的每一个极大点（边）双连通子图称作此无向图的点（边）双连通分量。

求双连通分量可用 Tarjan 算法。

若一个无向图中的去掉任意一个节点都不会改变此图的连通性，即不存在割点，则称作点双连通图。

一个无向图中的每一个极大点双连通子图称作此无向图的点双连通分量。

注意：一个割点属于多个点双连通分量。

代码实现：

//TODO

若一个无向图中的去掉任意一条边都不会改变此图的连通性，即不存在桥，则称作边双连通图。

一个无向图中的每一个极大边双连通子图称作此无向图的边双连通分量。

连接两个边双连通分量的边即是桥。

代码实现：

//TODO

注：部分资料来源于百度百科