支配树(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……谢谢啦~
2022年9月11日 01:09
Since the Government of AP also provided Computer labs for students in all Government schools also.Computer Knowledge is very much essential nowadays. Even Checking the Results of various examinations, AP SSC computer Question Paper Downloading hall tickets and study materials for multiple exams and booking tickets etc ..need minimum Technical Knowledge is much more important for everyone. Since the Government of AP also provided Computer labs for students in all Government schools also.