双连通分量

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

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

注意:如果图中有重边，且允许两个点形成一个环，则需修改对能否访问父节点的判断，即若当前边指向父节点，但不是从父节点走到当前点的边，则可以用父节点的dfn更新当前点的low。

注意:此代码不会将独立点记做一个连通分量。

1. 对图进行先深搜索，计算每一个结点v的先深标号dfn[v]。

2. 计算所有结点v的low[v]是在先深生成树上按照后根遍历的顺序进行的。因此，当访问结点v时它的每个儿子y的low[y]已经计算完毕，这时low[v]取下面三值中最小者:

(1) dfn[v];

(2) dfn[w], 凡是有回退边(v, w)的任何结点w;

(3) low[y],对v的任何儿子y.

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

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

这是初学者常见的问题，证明如下:

首先要明确边双连通分量和点双连通分量的区别与联系

1.二者都是基于无向图

2.边双连通分量是删边后还连通，而后者是删点

3.点双连通分量一定是边双连通分量(除两点一线的特殊情况)，反之不一定

4.点双连通分量可以有公共点，而边双连通分量不能有公共边

由于4，显然，求解边双连通分量只需先一遍dfs求桥，在一遍dfs求点(不经过桥即可)

但如果求点双连通分量，就要更复杂:

1.如果存边

根据dfs的性质，每条边都有且只有一次入栈，而由于性质3和性质4，点双连通分量没有公共边，所以弹出这个点双连通分量里的所有边就一定包含这里面的所有点，而且一定不含其他点双连通分量的边。因此求解时只需弹出这个点双连通分量里的所有边，并记录这些边的点即可(要判重，一个点可出现多次)，正确。

2.如果存点

根据dfs的性质，每个点同样有且只有一次入栈。但注意，由于性质4，你将一个点出栈后，还可能有别的点双连通分量包含它，错误。

有向图的最大强连通子图称为该有向图的强连通分量。

强连通图只有一个强连通分量，即本身，非强连通图有多个强连通分量。

任何连通图的连通分量只有一个，即为其本身。