【图论】支配树

最新推荐文章于 2019-09-27 16:45:56 发布

HOWARLI

最新推荐文章于 2019-09-27 16:45:56 发布

阅读量719

点赞数

分类专栏：支配树专题文章标签：支配树

本文链接：https://blog.csdn.net/HOWARLI/article/details/86726788

版权

专题同时被 2 个专栏收录

15 篇文章

订阅专栏

支配树

2 篇文章

订阅专栏

定义

支配树一般用来求有向图必经点问题，
即：给定起点S，问对于每个点i，S到i的必经点有哪些；

点i在支配树上父亲就是距离它最近的必经点，
显然的，必经点是具有一定传递性的，所以对于点i，S到i的所有必经点，就是支配树上i到根的路径上的所有点。

建树

首先，对于一棵树，它的支配树就是它本身；

对于一个DAG，它的支配树也很好求，
先排拓扑序，对于点i，它在支配树上的父亲就是所有能到达它的点在支配树上的LCA，这个挺好理解的，

那么对于一般的有向图呢?

先定义一些东西：dfn[x]表示x这个点的dfs序，

定义点y是点x的半支配点，当且仅当存在一条从y到x的路径 $y,v_1,v_2,v_3....,v_k,x$ ，满足 $dfn[v_i]>dfn[x](1\leq i \leq k)$ ，这条路径就叫它支配路径好了（捂脸）；
设semi[x]表示x的所有半支配点中，dfn最小的那个； 显然最小的是唯一的
（显然的，每个点semi至少是它在dfs树上的父亲）
定义idom[x]表示点x在支配树上的父亲（距离x最近的必经点）

通过定义可以得出一个结论：
结论1：删除原图中的非树边（dfs树），再添加边(semi[x],x)，支配树依旧不变。

证明：
我们考虑对于每个点x，删除它的其他入边并加上(semi[x],x)后，对全局的影响，
对于一个点，它的入边分成3类：

树边
父亲连过来(dfn小于当前点)
后代/横叉边(dfn大于当前点)

第一种边得到了直接的保留，不用管，

对于第二种，第三种边，这些边存在的意义就是提供一条路径，使得不经过 x到根路径上的树边也能从x的某一个祖先走过来，
而又因为如果y在semi[x]到x在dfs树的路径上（不含semi[x]），那么y一定不是x的必经点，也就是只要semi[x]提供了路径就够了，其他y没有必要再提供，

有了这个结论就可以把一般图转为DAG再用上面的方法了，复杂度： $O(n\log(n))$

要注意：semi不等于idom，通过semi我们只能确认idom一定不再semi[x]~x这段树上路径(不含semi[x])上，对于idom是否等于semi还需要分类讨论。

关于semi怎么求请继续往下看

接下来是 $O (n)$ 的方法
既然我们都把semi求出来了，考虑如何用semi推出idom，

有一个显然的结论：
结论2：对于点x，它到idom[x]的dfs树上路径中，一定不存在在路径上的点y，使得 dfn[idom[y]]<dfn[idom[x]]；

由此可以比较自然的再抛出一个结论：
结论3：设y为semi[x]~x树上路径上(不含semi[x])，dfn[idom[y]]最小的点，则idom[x]=(dfn[semi[x]]<dfn[idom[y]])?semi[x]:idom[y];
这个证明挺显然的，因为已经转成DAG了，归纳即可；

这个东西同理得：semi[y]是路径上所有的semi中dfn最小的；

这样我们就可以在得知semi后快速求出idom；

那么现在问题来了，怎么求出semi？

我们设 $best_x$ 表示点x的入边中，出发点dfn最小的点，（直接连向x的点中dfn最小的）

按dfn排序从大到小做，
我们做的过程相当于每次加入一个点x，dfn[x]一定是当前全局最小的，相当于加入了一个子树根，
（下面为了方便表示用min表示“取dfn最小的点”）
那么 $semi[x]=\min\{best[y](y可以到达x)\}$ （注意这里只能走已经加入了的点）
同样的 $semi[x]=\min\{semi[y](y可以到达x)\}$
同样的 $semi[x]=\min\{semi[y](y可以只经过一条树边到达x)\}$

也就是说，我们每加入一个新点x，设y为可以通过返祖边直接到达x的点，z为y~x树上路径上的点，则 $semi[x]=\min\{semi[z]\}$

这个可以通过带权并查集，利用其路径压缩的特性来做，（压缩每个点到当前根的路径）

求出了semi那怎么求idom呢，
我们只需要找到x~semi[x]的路径上（不含semi[x]）semi的dfn最小的点即可，

这个相当于询问一条祖先后代链上权值最小的点是哪个，
和上面一样的方案，只不过主体反过来了，我们把询问挂到dfn较小的那个点上，每次依旧是用带权并查集维护，

Code

这里给出的是CodeChef上GRAPHCNT这一题的标，
这题就是个版子题。

#include <cstdio>
#include <algorithm>
#include <iostream>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define efo(i,q,I) for(int i=A[I][q];i;i=B[i][0])
#define min(q,w) ((q)>(w)?(w):(q))
#define max(q,w) ((q)<(w)?(w):(q))
using namespace std;
typedef long long LL;
const int N=200500;
int read(int &n)
{
	char ch=' ';int q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n;
}
int m,n;
LL ans;
int B[15*N][2],A[4][N],B0;
int dfn[N],dfn0,Dzx[N],Fa[N];
int g[N],gv[N];
int semi[N],idom[N];
bool z[N];
int gf(int q){return g[q]==q?q:(gf(g[q]),(gv[q]=(dfn[semi[gv[g[q]]]]<dfn[semi[gv[q]]])?gv[g[q]]:gv[q]),g[q]=g[g[q]]);}
void link(int q,int w,int I)
{
	B[++B0][0]=A[I][q],A[I][q]=B0,B[B0][1]=w;
}
void tarjan(int q)
{
	z[q]=1;Dzx[dfn[q]=++dfn0]=q;
	efo(i,q,0)
	{
		if(!z[B[i][1]])tarjan(B[i][1]),Fa[B[i][1]]=q;
		if(dfn[semi[B[i][1]]]>dfn[q])semi[B[i][1]]=q;
	}
}
void Gsemi()
{
	fo(i,1,n)g[i]=gv[i]=i;
	fod(I,dfn0,1)
	{
		int q=Dzx[I];
		efo(i,q,1)if(dfn[B[i][1]]>dfn[q])
		{
			gf(B[i][1]);
			if(dfn[semi[gv[B[i][1]]]]<dfn[semi[q]])semi[q]=semi[gv[B[i][1]]];
		}
		gv[q]=q;
		link(semi[q],q,2);
		efo(i,q,2)if((gf(B[i][1]),semi[gv[B[i][1]]])==q)idom[B[i][1]]=q;
		else idom[B[i][1]]=gv[B[i][1]];

		efo(i,q,0)if(dfn[B[i][1]]>dfn[q]&&g[B[i][1]]==B[i][1])g[B[i][1]]=q;
	}
	fo(i,2,dfn0)
	{
		int q=Dzx[i];
		if(idom[q]!=semi[q])idom[q]=idom[idom[q]];
	}
}
int Si[N];
int dfs(int q,int fa)
{
	Si[q]=1;
	efo(i,q,3)if(B[i][1]!=fa)Si[q]+=dfs(B[i][1],q);
	return Si[q];
}
int main()
{
	int q,w;
	read(n),read(m);
	fo(i,1,m)read(q),read(w),link(q,w,0),link(w,q,1);
	fo(i,1,n)semi[i]=i;
	tarjan(1);
	Gsemi();
	idom[1]=0;
	fo(i,1,n)if(idom[i])link(idom[i],i,3);
	
	dfs(1,0);
	ans=q=0;
	efo(i,1,3)
	{
		ans+=(LL)q*Si[B[i][1]];
		q+=Si[B[i][1]];
	}
	printf("%lld\n",ans+Si[1]-1);
	return 0;
}