圆方树

SE の摆烂窝 / 2023-08-11 / 原文

构建

在将图变为树的方法里，圆方树与 v-dcc 类似。

圆方树中，原来的每个点对应一个圆点，每个点双对应一个方点。

故圆方树的节点数为 \(n+c\)，其中 \(n=|V|\)，\(c=|\text{v-dcc}|\).

对于每个点双，其方点向这个点双里的每个点连边，形成一个菊花图，多个菊花图通过割点连接。

割点的数量小于 \(n\)，故圆方树的点数小于 \(2n\).

若原图有 \(k\) 个连通分量显然圆方树森林有 \(k\) 颗树。

过程

Algorithm

考虑对每个连通子图构建它的圆方树。

圆方树使用的算法是 tarjan 的变体：对图 dfs，得到两个数组 \(dfn\) 和 \(low\).

\(dfn[u]\) 为 \(u\) 的 dfs 序。
\(low[u]\) 为 \(u\) 的 dfs 树的子树中的某个点 \(v\) 通过 最多一次返祖边或向父亲的树边 能访问到的最小 dfs 序。

和割点不同的是规定了可以通过父边向上，实际上和 tarjan 的实现基本相同。

Observation

每个点双在 dfs 树上是一颗连通子树，且至少包含两个点。特别地，最顶端节点仅往下接一个点。
每条树边恰好在一个点双内。

考虑一个点双在 dfs 树中的最顶端节点 \(u\)，那么 \(u\) 的子树包含了整个点双的信息。

再看点双的下一个点 \(v\)，那么 \(u,v\) 之间存在树边。

此时有 \(low[v]=dfn[u]\).

也就是，对于树边 \(u\rightarrow v\)，\(u,v\) 在一个点双里，且 \(u\) 在点双中的深度最浅当且仅当 \(low[v]=dfn[u]\).

确定点双的点集用类似 tarjan 的方法即可。

在栈中被弹出的节点，将其和新建的方点连边。最后让 \(u\) 和方点连边。

code

处理有多个连通子图的情况。

int n,m,cnt;
vector<int>e[N],T[N<<1];
int dfn[N],low[N],dfc;
int st[N],top;
void tarjan(int u){
	low[u]=dfn[u]=++dfc;
	st[++top]=u;
	for(int v:e[u]){
		if(!dfn[v]){
			tarjan(v),low[u]=min(low[u],low[v]);
			if(low[v]==dfn[u]){
				cnt++;
				for(int x=0;x!=v;top--){
					x=st[top];
					T[cnt].pb(x),T[x].pb(cnt);
				}
				T[cnt].pb(u),T[u].pb(cnt);
			}
		}
		else low[u]=min(low[u],dfn[v]);
	}
}
int main(){
	n=read(),m=read();
	cnt=n;
	for(int i=1,u,v;i<=m;i++){
		u=read(),v=read();
		e[u].pb(v),e[v].pb(u);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])tarjan(i),top--;
	
	return 0;
}

例题

P4630 [APIO2018] 铁人两项

一张简单无向图，问有多少三元组 \((s,c,f)\)，满足 \(s\not=c\not=f\)，且存在一条从 \(s\) 出发，经过 \(c\) 到达 \(f\) 的简单路径。

点双中的两点之间简单路径的并集恰好完全等于这个点双。

这个性质证明比较困难。

也是就是点双中的两个不同点 \(u,v\) 之间一定存在一条简单路径经过点双内的另一点 \(w\).

然后推出另一个结论：

对于两圆点在圆方树上的路径，“与路径上经过的方点相邻的圆点” 的集合等于原图中两点简单路径上的点集。

固定 \(s,f\)，合法的 \(c\) 的数量等于 \(s,f\) 之间简单路径的并集的点数 \(-2\).

考虑在圆方树上计数。

在圆方树上有一个 trick：路径统计时给点赋一个合适的权值。

对方点赋值为对应点双的大小，圆点赋值为 \(-1\).

那么两圆点间路径点权和即原图中简单路径并集大小 \(-2\).

现在要对每对圆点求和。

把它变成权值 \(\times\) 经过它的路径数，简单树形 DP。

我的圆方树写了个逆天错误调了一个小时。

#include<bits/stdc++.h>
#define ll long long
#define N 100010
#define pb push_back
using namespace std;
int read(){
	int x=0,w=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*w;
}
int n,m,cnt;
vector<int>e[N],T[N<<1];
int dfn[N],low[N],tim;
int st[N],top;
int val[N<<1],siz[N<<1];
int num;
void tarjan(int u){
	low[u]=dfn[u]=++tim;
	st[++top]=u;
	num++;
	for(int v:e[u]){
		if(!dfn[v]){
			tarjan(v),low[u]=min(low[u],low[v]);
			if(low[v]==dfn[u]){
				cnt++;
				for(int x=0;x!=v;top--){
					x=st[top];
					T[cnt].pb(x),T[x].pb(cnt);
					++val[cnt];
				}
				T[cnt].pb(u),T[u].pb(cnt);//这一步一开始搞错地方了
				++val[cnt];
			}
		}
		else low[u]=min(low[u],dfn[v]);
	}
}
ll ans;
void dfs(int u,int fa){
	siz[u]=(u<=n);
	for(int v:T[u]){
		if(v==fa)continue;
		dfs(v,u);
		ans+=2ll*val[u]*siz[u]*siz[v];
		siz[u]+=siz[v];
	}
	ans+=2ll*val[u]*siz[u]*(num-siz[u]);
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++)val[i]=-1;
	cnt=n;
	for(int i=1,u,v;i<=m;i++){
		u=read(),v=read();
		e[u].pb(v),e[v].pb(u);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i]){
			num=0;
			tarjan(i),top--;
			dfs(i,0);
		}
	printf("%lld\n",ans);
	
	return 0;
}

Tourists

简单无向连通图。支持：