支配树(Dominator tree)及Lengauer_Tarjan算法
冬令营时wmd大爷的营员交流是这个,当时完全没听懂,现在补了下。
Upd:一补就是2天……
本文大量参考:
[1] Tarjan著 王梦迪译 《在流程图中求支配点的一种快速算法》
[2] 王梦迪《支配树》——WC2016营员交流
[3] 李煜东《图连通性若干拓展问题探讨》——WC2014讲课
主要是参考[1][2],关于有向图的一些定义参考了[3]。
定义:
流程图(flowgraph):G=(V,E,r),是一张有向图,从r开始能走到任意一个点。
深度优先搜索(DFS):按深度优先的顺序对图进行遍历。在这里默认下文点的标号都是DFS序重标的号!
支配(dominate):x支配y的意思是x≠y,且从r开始到y的每一条路径都经过x。x是y的支配点(dominator)。
最近支配点(immediate dominator,下文简称idom):若y≠r且x支配y,且y的其余支配点全都支配x,则称x是y的最近支配点。
半支配点(semidominator,下文简称sdom):若y≠r,则sdom(y)=min{x|存在路径V0,V1..Vk使得V0=x,Vk=y,对于0<i<k都有Vi>y}。
半支配点的定义和支配好像关系不大,但是它的性质却可以用来方便地求最近支配点。
显然sdom(x)<=father(x)<x。
几个标记:
G,r如上所述。
T指的是DFS生成树。
".->"的意思是如果x.->y,则x是y在T上的祖先。
"+->"的意思是如果x+->y,则x是y在T上的完全祖先,即x.->y且x≠y。
关于有向图的边的定义:
树边(tree arcs):在T上的边。
前向边(forward arcs):从T上祖先到后代的边。
后向边(cycle arcs):从T上后代到祖先的边。
横叉边(cross arcs):两个点没有祖先后代的关系。
由DFS的性质,横叉边一定是从编号大的点指向小的点。
定理1(支配树定理):
除了r以外每个点都有唯一的idom,且不成环,即(idom(x),x)形成一棵树,x支配y当且仅当x是y的完全祖先。
注意支配树并不就是T,T是DFS生成树。
引理1(路径引理):
如果x<=y,则x到y的任意路径都包含它们在T中的一个公共祖先。
证明:横叉边只从大到小。再加上一些DFS的性质可证。
引理2:
idom(x)+->x.
证明:idom(x)在所有r到x的路径上,显然也在T中r到x的路径上。
引理3:
sdom(x)+->x.
因为sdom(x)<=father(x)<x,由引理1,从sdom(x)到x的符合条件的那条路径V0..Vk中,一定有个点a是sdom(x)和x的公共祖先。
而在T中,祖先的编号一定<=后代的编号,那么a<=sdom(x),又由定义对于0<i<k有Vi>x,所以a只能=V0。证毕。
引理4:
idom(x).->sdom(x).
两者都是x的祖先,而idom(x)不可能是sdom(x)的完全后代,否则存在路径r~sdom(x)~x,sdom(x)<idom(x)<x所以idom(x)不在这条路径上,不满足支配的定义。
引理5:
如果x.->y,则idom(y)要么是x的后代要么是idom(x)的祖先。
即如果x.->y,则x.->idom(y)或idom(y).->idom(x)。
反证:假设idom(x).->idom(y).->x.->y,那么由最近必经点的定义,idom(x)~x可以不经过idom(y),那么就存在路径r~idom(x)~x~y不经过idom(y)。
下面的定理2,3描述怎么用sdom求idom,定理4描述怎么求sdom。
定理2:
如果所有使得sdom(w)+->u.->w的u都满足sdom(u)>=sdom(w),则idom(w)=sdom(w)。
由引理4,idom(w).->sdom(w),只需证明sdom(w)支配w。
随便找一条r~w的满足存在一个点<sdom(w)的路径。
如果这样的路径一条都找不到,说明sdom(w)=r,支配w。
设x是这条路径上最后一个<sdom(w)的点,设y是这条路径上x之后第一个sdom(w).->y.->w的点,设x~y的路径为V0..Vk(V0=x,Vk=y)。
断言:对于所有0<i<k有Vi>y。
因为根据引理1,如果某个Vi<y,则有j>=i满足Vj是x和y的公共祖先。
根据x的选法,Vj>=sdom(w),而Vj又是y的祖先,一定有sdom(w).->Vj.->y.->w。和y的选法矛盾。
那么x就满足y的sdom定义的条件。
那么sdom(y)<=x<sdom(w)。而定理的条件中sdom(y)>=sdom(w),因此y不可能是sdom(w)的完全后代。只能y=sdom(w)。
也就是sdom(w)在这条路径上。因为这条路径是任选的,所以sdom(w)支配w。
定理3:
设u是所有满足sdom(w)+->u.->w中,sdom(u)最小的点,则idom(w)=idom(u)。
假设已经得到sdom,那么根据定理2、3已经可以求出所有点的idom。即idom(w)=((u=Min...)==w?sdom(w):idom(u))。
定理3是为什么呢?
根据引理5,要么u.->idom(w),要么idom(w).->idom(u)。即idom(w)要么是u的后代要么是idom(u)的祖先。
而idom(w).->sdom(w),所以只能是后者。
只需证明idom(u)支配w。
仿照定理2,考虑r~w的任意路径p上最后一个<idom(u)的点x及x之后第一个idom(u).->y.->w的点y。(若无此x,则idom(u)=r支配w)
类似的,对于0<i<k,Vi>y,sdom(y)<=x<idom(u)<=y。
断言:y不可能是idom(u)的完全后代,否则存在路径r~sdom(y)~y~u不经过idom(u)。
//是u还是w……?突然发现这里有点问题……先坑着
所以idom(u)=y。idom(u)在任意路径p上。idom(u)支配w。
定理4:
sdom(w)=min{ {v|(v,w) in E且v<w} U {sdom(u)|u>w且有边(v,w),u.->v} }.
//个人感觉前面v<w的条件是不必要的。正确性显然,也似乎不影响证明。
//王梦迪冬令营的PPT里画的第一幅图好像是错的……?出现了从小到大的横叉边233,解决方法一是去掉v<w的条件,二是把图画成树枝边。
证明是设等号右端是x,先证sdom(w)<=x,再证sdom(w)>=x。
sdom(w)<=x:充分性:显然。等号右端的式子满足sdom(w)的定义。
sdom(w)>=x:必要性:
设sdom(w)~w的路径V0=sdom(w)..Vk=w满足对于0<i<k有Vi>w。
如果k=1,满足x中第一种。
如果k≠1,设Vj是满足j>=1,第一个Vj.->Vk-1的。仿照定理2和3的证明,对于0<i<j,Vi>Vj。否则存在某个Vs.->Vj.->Vk-1,与Vj的定义矛盾。
所以sdom(w)满足sdom(Vj)的定义式。sdom(w)<=sdom(Vj)。而sdom(Vj)满足x中第二种,故x<=sdom(Vj)<=sdom(w)。证毕。
综上,sdom(w)=x。
算法流程:
先跑出T并把节点重新编号。
然后倒序扫描所有点,假设当前节点为x,用并查集维护所有点到最后一个>=x的点的父亲的信息(链上sdom最小点)。求出所有sdom。
在求sdom的时候把一个点挂在它的sdom上面,然后顺便跑出“sdom(w)+->u.->w”的这个u。具体实现起来可以在Father的最后一个儿子上面做。CC上有些标程是在所有点的父亲上都做一遍,我觉得复杂度是错的。
最后再根据每个点的u满足定理2还是定理3,来顺着跑出真正的idom即可。
复杂度O((n+m)*α(n))。冬令营上提问说O(n log n)的小哥是搞笑么……
Upd:事实证明是我自己搞笑啦……只路径压缩是O(log n)的……
模板题:
Codechef:GRAPHCNT
给出一张有向图,不保证是流程图,问有多少无序对(x,y),满足存在1~x和1~y的路径,除了1没有公共点。
两个点(x,y)不能成为答案当且仅当其中一个到不了,或者它们有除了1以外的公共必经点。
那么跑出Dominator Tree以后算下就行了。
#include<cstdio> #include<vector> #include<cctype> #include<cstring> #include<algorithm> #define For(i,x,y) for (int i=x;i<y;i++) #define Pb push_back using namespace std; int IN() { int c,f,x; while (!isdigit(c=getchar())&&c!='-');c=='-'?(f=1,x=0):(f=0,x=c-'0'); while (isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0';return !f?x:-x; } typedef long long LL; typedef double Db; const int N=100000+19,M=500000+19; typedef int one[N]; struct Edge {int y,nxt;} E[3*N+M]; one Last,DFN,Min,Fa,fa,idom,sdom,Pos,Dom,rev,S; int n,m,x,y,Time,cnt; vector<int> V[N]; LL Ans; void Add_Edge(int *Last,int x,int y) {E[cnt]=(Edge){y,Last[x]};Last[x]=cnt++;} int Getf(int x) { if (fa[x]==x) return fa[x]; int f=Getf(fa[x]); if (sdom[Pos[fa[x]]]<sdom[Pos[x]]) Pos[x]=Pos[fa[x]]; return fa[x]=f; } void DFS(int x) { int dx,dy,y; dx=DFN[x]=++Time; For(i,0,V[x].size()) if (!DFN[y=V[x][i]]) { DFS(y);dy=DFN[y]; Add_Edge(Last,dx,dy); Fa[dy]=dx;Min[dx]=min(Min[dx],dy); } } void Dominator() { For(i,1,n+1) idom[i]=sdom[i]=fa[i]=Pos[i]=i; for (int x=n;x>=2;x--) { for (int i=rev[x],y;~i;i=E[i].nxt) { Getf(y=E[i].y),sdom[x]=min(sdom[x],sdom[Pos[y]]); } Add_Edge(Dom,sdom[x],x); fa[x]=Fa[x]; if (x!=Min[Fa[x]]) continue; for (int i=Dom[Fa[x]],w;~i;i=E[i].nxt) { Getf(w=E[i].y),idom[w]=Pos[w]; } } memset(Dom,-1,sizeof(Dom)); For(x,2,n+1) { int u=idom[x]; idom[x]=(u==x?sdom[x]:idom[u]); Add_Edge(Dom,idom[x],x); } } int main() { freopen("GRAPHCNT.in","r",stdin); freopen("GRAPHCNT.out","w",stdout); memset(rev,-1,sizeof(rev)); memset(Dom,-1,sizeof(Dom)); memset(Last,-1,sizeof(Last)); memset(Min,60,sizeof(Min)); n=IN(),m=IN(); For(i,0,m) x=IN(),y=IN(),V[x].Pb(y); DFS(1); For(x,1,n+1) if (DFN[x]) For(i,0,V[x].size()) if (DFN[y=V[x][i]]) Add_Edge(rev,DFN[y],DFN[x]); n=Time; Dominator(); for (int i=n;i>=2;i--) S[i]++,S[idom[i]]+=S[i]; S[1]++; Ans=1LL*S[1]*(S[1]-1)/2; for (int i=Dom[1];~i;i=E[i].nxt) Ans-=1LL*S[E[i].y]*(S[E[i].y]-1)/2; printf("%lld\n",Ans); }
2016年2月05日 21:11
我觉得说 nlogn的小哥说的是并查集是logn的
2016年2月05日 22:18
@路人A: 嗯……?他的意思是不能路径压缩,只能按秩合并吧?
2016年2月05日 23:07
你这样写的并查集似乎是可以卡到logn的
2016年2月07日 11:52
@路人A: 嗯?我的不就是正常向的路径压缩吗QwQ
2016年2月15日 19:51
@RXDoi: 这样的路径压缩均摊是logn的,可以看下WC2015均摊分析简介
2016年2月16日 14:52
@路人A: 嗯。原来是这样。我对并查集复杂度的理解一直是错的QAQ……谢谢啦~