广义圆方树
stripe_python · · 算法·理论
圆方树刻画的是点双缩点后的结构。具体来说,我们用方点来代表一个点双,在方点下挂圆点表示点双中的点。
对于广义圆方树,我们要求圆点和方点间隔连接。贺一下 OI-Wiki 上的图
考察两个圆点
下文只讨论原图连通且不为单点的情形。可以使用如下 Tarjan 算法建圆方树:
int dn, cnt, dfn[N], low[N];
stack<int> st;
void tarjan(int u) {
dfn[u] = low[u] = ++dn, st.emplace(u);
for (int v : e[u]) {
if (!dfn[v]) {
tarjan(v), chkmin(low[u], low[v]);
if (low[v] != dfn[u]) continue;
int x; add(u, ++cnt);
do x = st.top(), st.pop(), add(x, cnt);
while (x != v);
} else {
chkmin(low[u], dfn[v]);
}
}
}
由于点双的数目
建出圆方树后,我们可以刻画原图的点双和边双在树上的形态:
- 点双:对应着每个度数
>2 的方点的邻域圆点。 - 边双:割边对应度数
=2 的方点,删去以后形成若干连通块即为边双,注意特判重边。
至此,使用广义圆方树 & DFS 生成树就足以刻画大部分无向图连通性问题。
CF487E Tourists
建立原图的广义圆方树,变成单点修改,询问一条毛毛虫的点权
上面的做法有点魔怔,考虑将圆点的权值挂在方点上,方点开个 multiset 维护,树剖线段树维护树链最小值即可。
P4606 [SDOI2018] 战略游戏
建立原图的广义圆方树,并对询问的点集建虚树,答案就是虚树的圆点数目。
根据经典结论,只要求出两两 dis 之和的一半即为答案。