双连通分量

无向图的双连通分量跟有向图的连通分量很像。

先说说一些定义。

时间戳：以某个点为起点，dfs到的其他点的时间。通常用$pre[i]$表示

连通图：任意两个点间都有路径存在的无向图就叫连通图。

割顶(cut vertex)：也叫割点。在某个连通图$G$中，若去掉某个点$i$，该图$G$无法保持所有点连通，那这个点就是割顶。

桥(bridge)：类似的，在某个连通图$G$中，若去掉某个边$e$，该图$G$无法保持所有点连通，那这个边就叫桥。

点-双连通：

若一个无向图的点两两间都有两条不相交（经过的点不一样）的路径，那么我们就称这个无向图是点-双连通的。条件等价于任意两条边都在一个简单环内。

不难发现，若一个无向图是点-双连通图，那么就代表这个图内部无割顶（既然有两条不相交的路径，去掉任何一个点都还是可以连通的）。

边-双连通：

类似的，若一个无向图的点两两间都有两条不重合（这个要求低一点，点可以重复，但边不行）的路径，那么我们就称这个无向图是边-双连通的。

在边-双连通图中，去掉任何一条边，这个图都还是连通的。

下面进入正题：

对于一张无向图，它的点-双连通的极大子图称为双连通分量(Biconnected Component,BCC)。

而边-双连通的极大子图称为边-双连通分量(edge-biconnected component)。

如上图：虽然{3,4,5}也是点-双连通的，但{3,4,5,6,7}才叫双连通分量，这就是极大子图的意义。另外一个双连通分量是{1,2,3}。还有，整个图{1,2,3,4,5,6,7,8}是边-双连通分量。

因为点-双连通分量比边-双连通分量更常见更难一些，所以接下来我们只讨论点-双连通分量，至于边-双连通分量就交给各位自己思考了。

还如上图：对于整个图来说，3是割顶。不难发现作为割顶的点会同时存在于多个双连通分量里。而其他点只可能存在于一个双连通分量里。

也正因为割顶会同时属于多个双连通分量，所以对于双连通分量来说，割顶无意义。

找双连通分量首先要会找割顶。

我们先随便找一个点作为根，强行把无向图转换为一棵树。连回父辈的边我们叫它反向边。

不难发现：若某个点$v$的后代都没有反向边连回$v$的父辈，而是最多只连回$v$，那么就可以得出$v$是割顶的结论。因为这样一来，去掉点$v$后，就会多了由点$v$的后代组成的连通分量。

用一个数组保存当前点

用时间戳$pre_i$就可以知道祖孙关系。

再开一个数组$low$。

$low_i$表示点$i$的子孙以及他自己所能访问到的点的$pre_i$的最小值。

注意：用反向边更新$low$数组时，不能用连回父亲的边，这条边没意义。

再用$pre_i$与$low_i$比较，就能知道点$i$是不是割顶。

当我们发现一个割顶点$u$时，说明我们找到了一个双连通分量。并且这个双连通分量由我们刚才访问完点$u$后遍历到的点组成。

考虑到需要知道的是最后访问的几个点，而且割顶会同时属于多个双连通分量，记录走过的点不太好，所以我们用一个栈记录走过的边。

当我们发现某个点是割顶时，就把栈里面的边拿出来，再把边上未染色的或者是颜色不同的点染色（赋值为$bccN$，表示这个点是属于编号为$bccN$的双连通分量的。若一个点之前就被被染过其他色，说明这个点是割顶）。

并用一个$vector$的二维数组保存这些点，表示编号为$bccN$的双连通分量里有这个点。

然后我们就可以找出所有双连通分量。

具体细节还得看代码。