支配
在有向图G
中,存在源点s
,若从s
出发的到达点y
的路径都经过点x
,称x
支配y
。
注意:若源点s
有多个,则可以虚拟一个起点
- 性质1.源点
s
支配所有的点,点x
一定支配x
本身 - 性质2.支配的传递性,若
x
支配y
,y
支配z
,则x
支配z
- 性质3.若
x
支配y
,y支配x,则有x=y
- 性质4.若
x
支配z,y
也支配z
,则x
和y
之间一定存在支配关系
这几条性质是显然的,就不证明了
支配树
定义dom[i]
表示支配点i
的点集,定义idom[i](immediate dominator)
表示支配点i
的点集中离i
最近的且不等于i
的点
- 性质5.除了源点
s
,所有点i
都有唯一的idom[i]
根据性质5,将点i
指向idom[i]
即可得到一棵树,称之为原有向图的支配树
- 性质6.支配树的根节点为原图的源点
s
- 性质7.支配树上点
i
的所有祖先节点就是点集dom[i]
根据性质4,点集dom[i]
会形成一条支配链,则性质7得证
应用场景
无向图的必经点的分析工具是圆方树,有向图的必经点分析工具是支配树
DAG(有向无环图)的支配树
对于DAG
的拓扑序,显然拓扑序大的结点不可达拓扑序小的结点,进而拓扑序大的结点不能支配拓扑序小的结点。
对于点y
,其idom[y]=lca(x1,x2,...,xk)
,其中x1,x2,...,xk
表示y
的所有入边的点,lca
为最近公共祖先
具体实现的时候每个点加入树的时候处理一下倍增信息,总时间复杂度O(nlogn)
例题
P2597 [ZJOI2012] 灾难
板题
注意:题目没有保证只有一个源点
#include<bits/stdc++.h>
using namespace std;
int n;
long long sz[100];
vector<int> v[100000],v1[100000],v2[100000];
int dep[100000],dp[100000][51],siz[100000],si[100000];
int dom[100000];
inline int read(){
char ch;int x=0;bool f=false;
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=true;
for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
if(f) x=-x;
return x;
}
int lca(int a,int b){
if(dep[b]>dep[a]) swap(a,b);
int op=(dep[a]-dep[b]);
for(int i=50;i>=0;i--){
if(op<sz[i]) continue;
op-=sz[i];
a=dp[a][i];
}
if(a==b) return a;
op=dep[a];
for(int i=50;i>=0;i--){
if(op<sz[i]) continue;
if(dp[a][i]==dp[b][i]) continue;
op-=sz[i];
a=dp[a][i],b=dp[b][i];
}
return dp[a][0];
}
void get_lca(int now){
if(now==0) return;
int k=v1[now][0];
for(int i=1;i<v1[now].size();i++){
k=lca(k,v1[now][i]);
}
dom[now]=k;
dp[now][0]=k,dep[now]=dep[k]+1;
int op=dep[now];
v2[k].push_back(now);
//cout<<k<<" "<<now<<endl;
for(int i=1;i<=50;i++){
if(op<sz[i]) break;
dp[now][i]=dp[dp[now][i-1]][i-1];
}
}
void dfs(int now){
//cout<<"now: "<<now<<endl;
siz[now]=-1;
get_lca(now);
for(int i=0;i<v[now].size();i++){
int to=v[now][i];
siz[to]--;
if(siz[to]==0) dfs(to);
}
}
void dfss(int now,int fa){
//cout<<now<<endl;
for(int i=0;i<v2[now].size();i++){
if(v2[now][i]==fa) continue;
dfss(v2[now][i],now);
si[now]+=si[v2[now][i]];
}
}
int main(){
cin>>n;
sz[0]=1;
for(int i=1;i<=50;i++){
sz[i]=sz[i-1]*2;
}
int u,op=0;
for(int i=1;i<=n;i++){
op=0;
while(u=read()){
if(!u) break;
op++;
v[u].push_back(i);
v1[i].push_back(u);
siz[i]++;
}
if(!op){
v[0].push_back(i);
v1[i].push_back(0);
siz[i]++;
}
}
//for(int i=1;i<=n;i++) cout<<siz[i]<<endl;
dfs(0);
//cout<<"Yes"<<endl;
for(int i=0;i<=n;i++) si[i]=1;
dfss(0,-1);
for(int i=1;i<=n;i++) cout<<si[i]-1<<"\n";
return 0;
}
有向图的支配树
对有向图跑DFS
树,得到每个点的时间戳dfn[i]
,并约定点x<y
,当且仅当dfn[x]<dfn[y]
(注意,该约定在下文的半支配点中任然生效)
- 性质1.若
x<y
,则原图中x
到y
的所有路径都经过树上x
和y
的公共祖先
半支配点(semi-dominator)
半支配点与有向图支配树算法相关
注意:本节中的祖先为DFS
树上的祖先
定义一个点x(x!=s)
的半支配点为sdom[x]
。满足在原图上,存在一条路径从sdom[x]
到x
,除了x
和sdom[x]
之外的任意一点y
(必须存在y
),dfn[y]>dfn[x]
。且sdom[x]
是满足条件的点中dfs
序最小的。
- 性质2.sdom[x]<fa[x]
- 性质3.对于任意
x!=s
,sdom[x]
为x
在DFS
树上的祖先结点 - 性质4.对于任意
x!=s
,idom[x]
一定是sdom[x]
的祖先结点
对于性质4,假设idom[x]
不是sdom[x]
的祖先结点,那么根节点s
一定可以直接走到sdom[x]
,不经过idom[x]
。
根据sdom[x]
的定义,其可以不经过时间戳比x
更小的点到达x
, 而idom[x]
一定是x
的祖先,自然idom[x]<x
,所以sdom[x]
可以不经过idom[x]
走到x
,产生矛盾
- 定理1.对于任意点
x!=s
,如果点y
是sdom[x]
到x
路径上的一点且x!=y
,且任意y都满足sdom[y]>=sdom[x]
,那么idom[x]=sdom[x]
- 定理2.对于任意点x!=s,设y是sdom[x]到x路径上的一点,y!=x,且sdom[y]为这条路径上最小的点,若sdom[y]<=sdom[x],那么idom[x]=idom[y]
寻找有向图idom[x]的方法
对于任意x!=s
,设y
为sdom[x]
到x
路径上的点,y!=x
,且sdom[x]
为这条路径上最小的点,那么\(idom[x]=\begin{Bmatrix}sdom[x](sdom[y]=sdom[x])\\idom[y](sdom[y]<sdom[x])\end{Bmatrix}\)
于是只需要求出sdom[x]
即可
寻找有向图sdom[x]的方法
对于任意点x!=s
,设y1
为x
的祖先结点中在原图中存在边指向x
的最小点
设点p>x
,且p
能够通过原图的边到达点x
设y2
为所有p
中最小的sdom[p]
,那么:
全步骤
- 1.跑一棵生成树,得到
DFS
序 - 2.求出半支配点
sdom[x]
- 3.利用结论求出一部分点的
idom[x]
- 4.求出剩余点的
idom[x]