冬令营时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);
}

[取消回复评论]

昵称 登录 E-mail: *
Web:
Twitter:

当有新评论通过 E-mail 通知我

(输入验证码)

or Ctrl+Enter