支配树 !!!
这是今天小白讲的内容，于是晚上用支配树过了一道裸题(hdu4694)。
这里大概梳理一下。
我们有一个有向图，可以有环，然后给定一个起点 s 。
定义一个点 u 的支配集为 s 到 u 的每一条路径经过的点的交集，即 s 到 u 必经的点集。不过为了方便，以下讨论中点 u 的支配集均不包含 u 本身。
定义点 u 的支配点为点 u 的支配集中，离 u 最“近”的点，也就是说删掉点 u 的支配点过后，s 仍然可以到达 u 的支配集中别的点。
我们的目标就是要求出每个点的支配点。
dfn表示时间戳。首先这里有一个性质， DFS 有向图过后，若 dfn[u] < dfn[v]，且 u到 v 有边， 那么在 DFS 树中 u 一定是 v 的祖先。 原因是有向图的 DFS 树中不存在从 dfn 小的点到 dfn 大的点的横叉边。
对于点 u，所有能够通过一些点 i 满足 dfn[i] > dfn[u] (不包括起点和终点)到达点 u 的点中， dfn 值最小的点为点 u 的半支配点(semi) 。即可以不经过点 u 的祖先到达点 u 的点中，dfn 最小的点。注意这个点一定是点 u 的祖先，这也是很容易就可以证明的。
半支配点看起来很像支配点，但实际上并不一定是。
比如这张图中，X 的半支配点就并不是 X 的支配点。(图片引自某博客)
不过没有关系，我们先考虑怎么求出半支配点。
对于一个点 u，若存在一条边 v -> u，这时我们考虑更新 u 的 semi。分两种情况，若 dfn[v] < dfn[u]，说明 v 是 u 的祖先，直接用 v 更新 ；若 dfn[v] > dfn[u]，那么这是一条横叉边，也就是说我们可以先走到点 v，再走到点 u，所以，这时我们应该用 v 和 v 的祖先中，不是 u 的祖先的点的 semi 来更新，因为我们可以从这个 semi 走到点 v 的祖先再走到 v 再跨过这条横叉边到 u。
带权并查集维护一下即可。
再考虑我们求出 semi 后，如何求出支配点，以下称之为 idom。
唯一有可能导致出现问题的就是上面的图中那种交叉的情况。于是我们对于点 u，令 u 的 semi 为 t，考虑点 u 到 u 的 t 这条路径上(不含点 t)的点中，令点 v 是 semi 的 dfn 最小的点，若 v 的 semi 等于 t，说明没有出现交叉，于是 u 的 idom 即为 t ； 但是若 v 的 semi 不等于 t，那么就出现了交叉，此时点 u 的 idom 应该等于点 v 的 idom。
同样是用带权并查集维护。
至此，问题已经得到解决。
关于实现方面，我们应该按照 dfn 从大到小的顺序处理每一个点。并且注意求 semi 和求 idom 是可以写在一起的，而且带权并查集维护的东西也是一样的。代码也只有不到一百行。
hdu4694：
#include
#include
#include
#include
#include
#define my_min(a,b) ((a)<(b)?(a):(b))
#define my_max(a,b) ((a)>(b)?(a):(b))
using namespace std;
int reads(int &x)
{
bool f=false ; char t=(char)getchar() ; x=0 ;
while(t<'0'||t>'9'){
if(t=='-')f=true ;
if(t==EOF)return EOF;
t=(char)getchar() ;
}
while(t>='0'&&t<='9'){
x=(x<<1)+(x<<3)+t-'0' ;
t=(char)getchar() ;
}
if(f)x=-x ;
return 0 ;
}
int n , m , fa[50055] , val[50055] , dfn[50055] , TTT , q[50055] , qnum , semi[50055] , idom[50055] , ans[50055] ;
int ff[50055] ;
vector G1[50055] , G2[50055] , tag[50055] , G3[50055] ;
// val 存的是 semi 最浅的点的编号
void init(){
TTT=qnum=0 ;
for(int i=1;i<=n;++i)fa[i]=i , G1[i].clear() , G2[i].clear() , G3[i].clear() , tag[i].clear() , semi[i]=i , ans[i]=idom[i]=val[i]=0 ;
memset(dfn,0,sizeof(int)*(n+5)) ;
dfn[0]=(1<<30)-1 ;
//
}
inline void update_1(int &a,int b){ if(dfn[b]
inline void update_2(int &a,int b){ if(dfn[semi[b]]
int find_fa(int a)
{
if(fa[a]==a)return fa[a] ;
int tf=fa[a] ;
fa[a]=find_fa(fa[a]) ;
update_2(val[a],val[tf]) ;
return fa[a] ;
}
void dfs(int a,int f){
dfn[a]=++TTT , q[++qnum]=a , ff[a]=f ;
int len=(int)G1[a].size() ;
for(int i=0;i
int b=G1[a][i] ;
if(!dfn[b])dfs(b,a) ;
}
}
void get_idom(){
for(int i=qnum;i>=1;--i){
int a=q[i] , len=(int)G2[a].size() ;
for(int j=0;j
int b=G2[a][j] ;
if(!dfn[b])continue ;
if(dfn[b]
else find_fa(b) , update_1(semi[a],semi[val[b]]) ;
}
len=(int)tag[a].size() ;
for(int j=0;j
int b=tag[a][j] , t;
find_fa(b) , t=semi[val[b]] ;
if(t==a)idom[b]=a ;
else idom[b]=-val[b] ; // (debug) 这里不是 -t
}
if(i!=1) tag[semi[a]].push_back(a) ;
if(ff[a])fa[a]=ff[a] , val[a]=a ;
}
for(int i=2;i<=qnum;++i){
int a=q[i] ;
if(idom[a]<0)idom[a]=idom[-idom[a]] ;
}
}
void dfs_2(int a,int now){
int len=(int)G3[a].size() ;
ans[a]=now ;
for(int i=0;i
int b=G3[a][i] ;
dfs_2(b,now+b) ;
}
}
void solve(){
for(int i=1;i<=m;++i){
int a,b;
scanf("%d%d",&a,&b) ;
G1[a].push_back(b) , G2[b].push_back(a) ;
}
dfs(n,0) ;
get_idom() ;
for(int i=1;i<=n;++i)if(idom[i])G3[idom[i]].push_back(i) ;
dfs_2(n,n) ;
for(int i=1;i<=n;++i) printf((i==n?"%d\n":"%d "),ans[i]) ;
}
int main()
{
while(reads(n)!=EOF){
reads(m) ;
init() ;
solve() ;
}
return 0 ;
}
评论(2)