双连通分量

定义

分为点双和边双。若一个无向图的任意两点之间都有至少两条点/边不存在交集（除了起点终点）的路径，即删除任一点/边都不会改变原图的连通性，即原图不存在割点/割边，则称原无向图为点/边双连通分量。

性质

对于点双：

1. 任意非割点最多处于一个点双中。

2. 任意两个点双，若其交集不为空，则交集必为割点。即点双是由割点分割的。

3. 任意一个割点至少被两个点双所包含。

对于边双：类似的。

怎么求

以点双为例：在 tarjan 的时候用栈记录访问过的边和点，遇到割点时就从栈不断弹出，直到割点以及割点在 dfs 树上的父边也被弹出，则弹出的元素都在同一点双内。

pre[v]=id,stkid[++topid]=id,tarjan(v),low[u]=min(low[u],low[v]);
if(low[v]<dfn[u]) continue ;
int temp;
++DsccnPoint,++DsccnEdge;
do temp=stk[top--],DsccPoint[temp]=DsccnPoint;
while(temp!=v);
do temp=stkid[topid--],DsccEdge[tempo]=DsccnEdge;
while(temp!=pre[v]);

圆方树

用途

将仙人掌/一般图上的问题转换为树上问题。

狭义圆方树

主要用于解决仙人掌上的问题。

建图：对于每个环，将所有环边断掉，新建一个方点，再将环上所有（圆）点与这个方点相连。

广义圆方树

建图：将原图每一条边断掉，对于每一个点双新建一个方点，并将原图该点双中含有的点与这个方点相连。

性质

1. 相邻两点的类型一定不同。

2. 两点之间所有路径的交集等价于圆方树上这两个点之间的圆点。

3. 两点之间所有路径的并集等价于圆方树上这两个点之间的所有方点代表的点双的点集的并集。

4. 圆方树是无根树。