概述
圆方树(Block forest)是一种将图变成树的方法。
极大点双连通子图
一个图的 点双连通分量 是一个 极大点双连通子图,注意到,同时包含两个节点的 极大点双连通子图 如果存在,那么它是唯一的。
圆方树
在圆方树中,原来的每个点对应一个 圆点,每一个 点双连通分量 对应一个 方点。
不难发现,圆方树的点数小于 $2n$。
建树
其实就是用 tarjan 找 点双连通分量。
我们可以给方点标号为从 $n + 1$ 开始的整数,这样可以区分圆点和方点。
#include <algorithm>
#include <cstdio>
#include <vector>
const int MN = 100005;
int N, M, cnt;
std::vector<int> G[MN], T[MN * 2];
int dfn[MN], low[MN], dfc;
int stk[MN], tp;
void Tarjan(int u) {
printf(" Enter : #%d\n", u);
low[u] = dfn[u] = ++dfc; // low 初始化为当前节点 dfn
stk[++tp] = u; // 加入栈中
for (int v : G[u]) { // 遍历 u 的相邻节点
if (!dfn[v]) { // 如果未访问过
Tarjan(v); // 递归
low[u] = std::min(low[u], low[v]); // 未访问的和 low 取 min
if (low[v] == dfn[u]) { // 标志着找到一个以 u 为根的点双连通分量
++cnt; // 增加方点个数
printf(" Found a New BCC #%d.\n", cnt - N);
// 将点双中除了 u 的点退栈,并在圆方树中连边
for (int x = 0; x != v; --tp) {
x = stk[tp];
T[cnt].push_back(x);
T[x].push_back(cnt);
printf(" BCC #%d has vertex #%d\n", cnt - N, x);
}
// 注意 u 自身也要连边(但不退栈)
T[cnt].push_back(u);
T[u].push_back(cnt);
printf(" BCC #%d has vertex #%d\n", cnt - N, u);
}
} else
low[u] = std::min(low[u], dfn[v]); // 已访问的和 dfn 取 min
}
printf(" Exit : #%d : low = %d\n", u, low[u]);
printf(" Stack:\n ");
for (int i = 1; i <= tp; ++i) printf("%d, ", stk[i]);
puts("");
}
int main() {
scanf("%d%d", &N, &M);
cnt = N; // 点双 / 方点标号从 N 开始
for (int i = 1; i <= M; ++i) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v); // 加双向边
G[v].push_back(u);
}
// 处理非连通图
for (int u = 1; u <= N; ++u)
if (!dfn[u]) Tarjan(u), --tp;
// 注意到退出 Tarjan 时栈中还有一个元素即根,将其退栈
return 0;
}