算法复键——圆方树

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162103786

干什么的

把点双变成一个点

怎么实现

https://blog.csdn.net/zhangtingxiqwq/article/details/132645934

代码总览：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

void dfs(int x) {
	dfn[x]=low[x]=++tot; z.push(x); 
	for(int y : T[x]) {
		if(!dfn[y]) {
			dfs(y); 
			low[x]=min(low[x], low[y]); 
			if(low[y]==dfn[x]) {
				cun(x, ++num); 
				while(z.top()!=y) cun(z.top(), num), z.pop(); 
				cun(y, num); z.pop(); 
			}
		}
		else low[x]=min(low[x], dfn[y]); 
	}
}

1. 不用记录父亲，因为普通一条边也可以作为边双的一部分

2. 由于求的是边双而不是点双，所以判断应为 low[y]==dfn[x]，表示 $y$ 最多可以返祖到 $x$

关键解释：

1

dfn[x]=low[x]=++tot; z.push(x); 

1. ++tot ：时间戳自增，给 x 分配唯一访问序号；

2. dfn[x] = low[x] ：刚搜到 x，目前它能回退到的最小时间戳就是自己；

3. z.push(x) ：把 x 压入栈，后续用来提取一整个点双连通分量。

1

if(!dfn[y]) {

分支 1：y 没访问过，是子树节点，向下递归。

1
2

dfs(y); 
low[x]=min(low[x], low[y]); 

1. 递归搜儿子 y，搜完回来再更新 x 的 low。

2. 子树 y 能绕回更小的时间戳，x 也能走这条路，更新 low[x]。

1

if(low[y]==dfn[x]) {

从 y 往下走，最多只能绕回 x，说明 x 是割点，x–y 这条分支构成一个独立点双连通分量。

此时要新建一个方点，把栈里属于这个点双的所有圆点和方点连边。

1
2
3

cun(x, ++num); 
while(z.top()!=y) cun(z.top(), num), z.pop(); 
cun(y, num); z.pop(); 

++num ：方点编号+1，生成新虚拟方点；

循环弹栈：只要栈顶不是 y，说明栈顶圆点都属于当前这个点双。

到此，一整个点双对应的圆方树的一个 方点 全部建完。

1
2

}
else low[x]=min(low[x], dfn[y]); 

分支2：y 已经访问过（回边，不是父亲）
直接用 y 的时间戳 dfn[y] 更新 low[x]，代表 x 能通过回边绕到更早的点。