支配树

在一个有向图中，有一个起点R，对于任意点W，对于R->W的任意路径都经过点P，则称P为W的支配点。设idom[i]表示距离i最近的支配点。在原图基础上，idom[i]向i连边构成一颗新树，称为支配树

支配树的性质

1.支配树是以R为根的一棵树
2.对于任意点i，到根r路径上经过的点集{xi}是原图上r->i的必经点
3.对于任意的i，它是子树中每个点的必经点

求得

半必经点

在dfs搜索树中，对于一个节点Y，存在某个点X能够通过一系列点pi（不包含X和Y）到达点Y且?i dfn[i]>dfn[Y]，我们就称X是Y的半必经点，记做semi[Y]=X
通俗理解：semi[x]就是x在dfs树中所有祖先中z，能不经过 z? 和 x? 之间的树上的点而到达 x? 的点中深度最小的。

半必经点性质

1. semi[x]一定是x的祖先
2. semi[x]一定是确定的
3. 半必经点不一定是必经点
4. semi[x]深度不小于idom[x]，即idom[x]在semi[x]祖先链上

证明的话，咕咕了

半必经点的作用

保留dfs树的树边，连接semi[i]->i构建新图。不改变原图支配关系，且构成一个dag图。

计算

对于点x，有边(y,x)
? 若dfn[y]$<$dfn[x](树边或前向边） 且dfn[y]$<$dfn[semi[x]] ,semi[x]=y
? 根据定义显然
? 若dfn[y]>dfn[x]（后向边或横叉边），找到y的一个祖先semi值最小
的z且dfn[z]>dfn[x]，用semi[z]更新semi[x]

计算idom

性质

1. idom[x]的深度不大于semi[x]
2. 设点集P是semi[x]（不包含）到x路径上的点，t是P中semi最小的点(1、若semi[t]=semi[x],则idom[x]=semi[x]2、若semi[t]!=semi[x],则idom[x]=idom[t])

算法

1. 按dfs序搜索原图得到dfn，从dfn大到小考虑节点
2. 利用带权并查集维护每个点到祖先链上semi值最小值
3. 设当前计算semi[x],对于（y,x）若dfn[y]>dfn[x],则直接根据 更新（y的semi已经计算完）若dfn[y]$<$dfn[x]，则semi[y]没有更新，y是并查集独立点， 同样更新
4. 用x=semi[y]->y更新y的idom，直接查询y祖先链上最小值
5. 最后将semi[x]!=idom[x]的节点idom按dfn从小到大刷新一次

代码实现

HDU4694

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>fg[N];vector<int>gg[N];vector<int>ng[N];
int n,m,cnt,tot,rt;
int num[N],val[N],size[N],du1[N],du2[N],fa[N],dfn[N],semi[N],idom[N],fir[N],nxt[N],ver[N],col[N];
void init(){
    cnt=tot=rt=0;
    for(int i=1;i<=n;i++)fg[i].clear(),gg[i].clear(),ng[i].clear();
    memset(val,0,sizeof val);memset(num,0,sizeof num);
    memset(du1,0,sizeof du1);memset(du2,0,sizeof du2);
    memset(fa,0,sizeof fa);memset(dfn,0,sizeof dfn);
    memset(semi,0,sizeof semi);memset(idom,0,sizeof idom);
    memset(fir,0,sizeof fir);memset(nxt,0,sizeof nxt);
    memset(ver,0,sizeof ver);memset(col,0,sizeof col);
}
inline void add(int x,int y){ver[++tot]=y,nxt[tot]=fir[x];fir[x]=tot;}
void dfs(int x){
    dfn[x]=++cnt,num[cnt]=x;
    for(int i=fir[x];i;i=nxt[i]){
        int y=ver[i];if(dfn[y]) continue;
        fa[y]=x;dfs(y);
    }
}
int find(int x){
    if(col[x]==x) return x;
    int fx=find(col[x]);
    if(dfn[semi[val[col[x]]]]<dfn[semi[val[x]]]) val[x]=val[col[x]];
    col[x]=fx;return fx;
}
void tarjan(){
    for(int j=cnt;j>1;j--){
        int x=num[j];
        for(int i=0;i<fg[x].size();i++){
            int y=fg[x][i];if(!dfn[y]) continue;
            find(y);
            if(dfn[semi[val[y]]]<dfn[semi[x]])
                semi[x]=semi[val[y]];
        }
        gg[semi[x]].push_back(x);
        col[x]=fa[x];int now=fa[x];
        for(int i=0;i<gg[now].size();i++){
            int x=gg[now][i];
            find(x);
            if(semi[val[x]]==now) idom[x]=now;
            else idom[x]=val[x];
        }
    }
    for(int i=2;i<=cnt;i++){
        int x=num[i];
        if(idom[x]!=semi[x]) idom[x]=idom[idom[x]];
        ng[idom[x]].push_back(x);
    }
}
void dfsans(int x,int sum){
    du2[x]=x+sum;
    for(int i=0;i<ng[x].size();i++)
        dfsans(ng[x][i],sum+x);
}
int main(){
    //freopen("nmmp.cpp","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF){
    int x,y;init();
    for(int i=1;i<=m;i++) scanf("%d%d",&x,&y),add(x,y),fg[y].push_back(x);
    for(int i=1;i<=n;i++){col[i]=val[i]=semi[i]=i;}
    dfs(n);tarjan();dfsans(n,0);
    for(int i=1;i<n;i++) printf("%d ",du2[i]);
    printf("%d",du2[n]);puts("");
    }
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#pragma GCC optimize(3)
using namespace std;
const int    MAXN = 50000 + 10;
int        n, m;
int read()
{
    int        x    = 0, f = 1;
    static char    c    = getchar();
    while ( c<'0' || c>'9' )
    {
        if ( c == '-' )
            f = -1;
        c = getchar();
    }
    while ( c >= '0' && c <= '9' )
    {
        x = (x << 1) + (x << 3) + (c ^ '0'); c = getchar();
    }
    return(x * f);
}


struct Graph {
    vector<int>    G[MAXN];
    void        add( int f, int t )
    {
        G[f].push_back( t );
    }


    void reset()
    {
        for ( int i = 1; i <= n; i++ )
            G[i].clear();
    }
}        G, rG, sG, tree;
int        dfn[MAXN], id[MAXN], dfn_cnt, semi[MAXN], idom[MAXN], dep[MAXN];
int        degree[MAXN];
int        fa[MAXN];
int        lca[MAXN][20];
int        belong[MAXN], mn[MAXN]; /* bcj */
bool        vis[MAXN];
int        q[MAXN], top;
int        sum;
queue<int>    Q;
int        ans[MAXN];
void reset()
{
    dfn_cnt = 0; top = 0; sum = 0;
    memset( lca, 0, sizeof(lca) );
    memset( vis, false, sizeof(vis) );
    memset( fa, 0, sizeof(fa) );
    memset( degree, 0, sizeof(degree) );
    memset( dfn, 0, sizeof(dfn) );
    memset( id, 0, sizeof(id) );
    memset( semi, 0, sizeof(semi) );
    memset( dep, 0, sizeof(dep) );
    memset( ans, 0, sizeof(ans) );
    memset( mn, 0, sizeof(mn) );
    for ( int i = 1; i <= n; i++ )
    {
        belong[i] = i; mn[i] = i;
    }
    G.reset(), sG.reset(), tree.reset(), rG.reset();
}


void getdfn( int x, int f )
{
    dfn[x]    = ++dfn_cnt; id[dfn_cnt] = x;
    semi[x] = x; fa[x] = f;
    vis[x]    = true;
    for ( int i = 0; i < G.G[x].size(); i++ )
    {
        int t = G.G[x][i];
        if ( vis[t] )
            continue;
        getdfn( t, x );
    }
}


int find( int x )
{
    if ( x == belong[x] )
        return(x);
    int f = belong[x]; belong[x] = find( f );
    if ( dfn[semi[mn[f]]] < dfn[semi[mn[x]]] )
        mn[x] = f;
    return(fa[x]);
}


int LCA( int x, int y )
{
    if ( dep[x] < dep[y] )
        swap( x, y );
    int d = dep[x] - dep[y];
    for ( int i = 18; i >= 0; i-- )
        if ( d & (1 << i) )
            x = lca[x][i];
    for ( int i = 18; i >= 0; i-- )
    {
        if ( lca[x][i] ^ lca[y][i] )
            x = lca[x][i], y = lca[y][i];
    }
    return(x == y ? x : lca[x][0]);
}


void worklca( int x )
{
    int anc = sG.G[x][0];
    for ( int i = 0; i < sG.G[x].size(); i++ )
    {
        anc = LCA( anc, sG.G[x][i] );
    }
    dep[x]        = dep[anc] + 1;
    idom[x]        = anc;
    lca[x][0]    = anc;
    for ( int i = 1; i <= 18; i++ )
        lca[x][i] = lca[lca[x][i - 1]][i - 1];
}


void lengauer_tarjan()
{
    getdfn( n, 0 );
    dfn[0] = 0x3f3f3f3f;
    for ( int w = dfn_cnt; w > 1; w-- )
    {
        int x = id[w];
        for ( int i = 0; i < rG.G[x].size(); i++ )
        {
            int t = rG.G[x][i];
            if ( !dfn[t] )
                continue;
            find( t );
            if ( dfn[semi[mn[t]]] < dfn[semi[x]] )
                semi[x] = semi[mn[t]];
        }
        sG.add( semi[x], x );
        belong[x] = fa[x];
        int now = fa[x];
        for ( int i = 0; i < sG.G[now].size(); i++ )
        {
            int x = sG.G[now][i];
            find( x );
            if ( semi[mn[x]] == now )
                idom[x] = now;
            else idom[x] = mn[x];
        }
    }
    for ( int i = 2; i <= dfn_cnt; i++ )
    {
        int x = id[i];
        if ( idom[x] != semi[x] )
            idom[x] = idom[idom[x]];
        tree.add( x, idom[x] );
    }
}


int getans( int x )
{
    int ans = x;
    for ( int i = 0; i < tree.G[x].size(); i++ )
    {
        ans += getans( tree.G[x][i] );
    }
    return(ans);
}


int main()
{
    while ( scanf( "%d%d", &n, &m ) != EOF )
    {
        int f, t;
        reset();
        for ( int i = 1; i <= m; i++ )
        {
            f = read(), t = read();
            G.add( f, t ); rG.add( t, f );
        }
        lengauer_tarjan();
        for ( int i = 1; i <= n; i++ )
            printf( "%d ", getans( i ) );
        puts( "" );
    }
}

支配树

原文：https://www.cnblogs.com/BeyondStars/p/12380664.html