浅谈支配树

前言

这个神奇的东西我也是最近才听说，感觉挺神仙的，然后去写了一下模板题，再发一篇博客加深记忆。

支配点与半支配点

我们定义一个有向图中结点x关于结点s支配结点y，当且仅当在所有s通往y的路径中都经过了x，我们也称x是y关于s的支配点。

一个简单的问题是我们要找出对于任意一个点x找出支配它的点的个数。

首先这个暴力肯定是$O(n^3)$的，但是有一个Lengauer-Tarjan算法可以在$O(m\log_{1+m/n} n)$的时间复杂度内做出这个东西，我们可以来学习一下。

首先引入一个概念：半支配点。

我们先建立一棵根为s的dfs树，记点x的dfs序为$dfn(x)$，然后我们称y是点x的关于s的半支配点，当且仅当y存在一条通往x的路径，且对于路径上除y以外的所有点z，都有$dfn(z)\ge dfn(x)$。

对于点x，其dfs序最小的半支配点我们记为$semi(x)$，dfs序最大的支配点我们记为$idom(x)$。

显然$semi(x)$与$idom(x)$均为x在dfs树上的祖先。

另外可以证明，支配具有传递性，如果A支配了B，B支配了C，那么A也支配了C。所以，如果我们以$idom(x)$作为x的父亲建立一棵树，那么这棵树的一棵子树中的节点个数为该子树根支配的点的个数，能支配某一个点的点的个数是该节点到根节点上的节点个数。

Lengauer-Tarjan算法

这是一个很神奇的建树方法，大概意思就是先求semi，再用semi求idom。

首先我们建出dfs树，考虑如何求semi。

对于节点x，考虑这条路径的上一个节点是什么，我们先建出反图，找到所有存在边$y->x$的y，然后假如$dfn(y)<dfn(x)$那么y一定是x的祖先，直接转移一下就好了。

难点在于$dfn(y)>dfn(x)$的情况，我们需要找到所有路径中dfs序大于$dfn(x)$且能通过y到达x的路径起点，我们考虑按dfs序从大到小做，那么此时y的semi已经求出来了，路径上除了x的祖先以外可能有的节点的semi也已经求出来了，所以只需要求当前y到最高能到达的祖先这条路径上节点的$dfn(semi(z))$最小的节点，这个我们可以用一个并查集维护，把一棵子树做完之后把根的所有儿子并到根上。在路径压缩的时候顺带维护一下某个节点到当前根的路径上我们需要维护的值。

需要注意的是，我们的并查集不能按秩合并，所以时间复杂度不是摊还$O(\alpha(n))$的。它大概长这样吧：

struct DSF{
    int fa[MAX_N],key[MAX_N];
    int find_set(int x){
        if(fa[x]!=x){
            int p=fa[x];
            fa[x]=find_set(p);
            if(dfn[semi[key[p]]]<dfn[semi[key[x]]]) 
                key[x]=key[p];
        }
        return fa[x];
    }
    void link(int x,int y){ fa[y]=x; }
    void make_set(int x){ fa[x]=x,key[x]=x; }
    int get_key(int x){ //用于求出路径上semi值最小的结点
        find_set(x);
        return key[x];
    }
}dsf;
 

这个是求semi的代码(干脆把两种情况并在一起了）：

//G2是反图，G3是dfs树
        for(int j=G2.head[x];j!=-1;j=G2.edge[j].nxt){ 
            int y=G2.edge[j].to;
            if(dfn[y]==0) continue;
            y=dsf.get_key(y);
            if(dfn[semi[y]]<dfn[semi[x]])
                semi[x]=semi[y];
        }
        for(int j=G3.head[x];j!=-1;j=G3.edge[j].nxt){ //做完之后合并一下
            int y=G3.edge[j].to;
            dsf.link(x,y);
        }
 

是用$semi$求$idom$，考虑$x$到$semi(x)$这段路径，如果里面$semi$一个都没有超过$semi(x)$那么显然$idom(x)=semi(x)$，

如果有呢，那么就是$x$到$semi(x)$这段路径上$dfn(semi(x))$最小的节点的$idom(x)$（证明很简单，分类讨论一下就好了）。

但是我们在做的时候怎么求呢，我们再开一个边表，从x往$semi(x)$连一条边，然后还是用之前那个并查集维护出路径上$dfn(semi(z))$最小的点，但是这个时候我们发现$idom(semi(z))$可能还没有被求过，那么我们就记录一下，然后最后统一更新答案就好了。

代码很短。

        if(x!=s) G4.add_edge(semi[x],x);
        for(int j=G4.head[x];j!=-1;j=G4.edge[j].nxt){
            int y=G4.edge[j].to;
            int z=dsf.get_key(y);
            if(semi[z]==semi[y]) idom[y]=semi[y];
            else idom[y]=z;
        }
 

例题

这个由于刚刚进入OI领域不久所以只有模板题。

洛谷模板题代码：

#include<bits/stdc++.h>
using namespace std;
const int MAX_N=5+2e5;
struct Graph{
    struct Edge{ int to,nxt; }edge[MAX_N*2];
    int head[MAX_N],top_edge;
    Graph(){ top_edge=-1,memset(head,-1,sizeof(head)); }
    void add_edge(int x,int y){
        edge[++top_edge]=(Edge){y,head[x]};
        head[x]=top_edge;
    }
}G1,G2,G3,G4,G5;
int cnt[MAX_N],semi[MAX_N],idom[MAX_N],ti=0;
int dfn[MAX_N],id[MAX_N],fa[MAX_N];
struct DSF{
    int fa[MAX_N],key[MAX_N];
    int find_set(int x){
        if(fa[x]!=x){
            int p=fa[x];
            fa[x]=find_set(p);
            if(dfn[semi[key[p]]]<dfn[semi[key[x]]]) 
                key[x]=key[p];
        }
        return fa[x];
    }
    void link(int x,int y){ fa[y]=x; }
    void make_set(int x){ fa[x]=x,key[x]=x; }
    int get_key(int x){
        find_set(x);
        return key[x];
    }
}dsf;
void dfs(int x,int pre){
    dfn[x]=++ti,id[ti]=x,semi[x]=x,fa[x]=pre;
    for(int j=G1.head[x];j!=-1;j=G1.edge[j].nxt){
        int y=G1.edge[j].to;
        if(dfn[y]==0){
            G3.add_edge(x,y);
            dfs(y,x);
        }
    }
}
void solve(int n){
    idom[1]=1;
    for(int i=n;i>=1;--i){
        int x=id[i];
        if(dfn[x]==0) continue;
        for(int j=G2.head[x];j!=-1;j=G2.edge[j].nxt){
            int y=G2.edge[j].to;
            if(dfn[y]==0) continue;
            y=dsf.get_key(y);
            if(dfn[semi[y]]<dfn[semi[x]])
                semi[x]=semi[y];
        }
        if(x!=1) G4.add_edge(semi[x],x);
        for(int j=G4.head[x];j!=-1;j=G4.edge[j].nxt){
            int y=G4.edge[j].to;
            int z=dsf.get_key(y);
            if(semi[z]==semi[y]) idom[y]=semi[y];
            else idom[y]=z;
        }
        for(int j=G3.head[x];j!=-1;j=G3.edge[j].nxt){
            int y=G3.edge[j].to;
            dsf.link(x,y);
        }
    }
    for(int i=2;i<=n;++i){
        int x=id[i];
        if(dfn[x]==0) continue;
        idom[x]=idom[x]==semi[x]?semi[x]:idom[idom[x]];
        G5.add_edge(idom[x],x);
    }
}
void dfs2(int x){
    cnt[x]=1;
    for(int j=G5.head[x];j!=-1;j=G5.edge[j].nxt){
        int y=G5.edge[j].to;
        dfs2(y);
        cnt[x]+=cnt[y];
    }
}
int main(){
    int n,m; scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int x,y; scanf("%d%d",&x,&y);
        G1.add_edge(x,y);
        G2.add_edge(y,x);
    }
    for(int i=1;i<=n;++i) dsf.make_set(i);
    dfs(1,0);
    solve(n);
    dfs2(1);
    for(int i=1;i<=n;++i) printf("%d ",cnt[i]);
    return 0;
}