支配树学习笔记

之前从《算法竞赛进阶指南》有听说过这个算法当时每太注意。近段时间多校遇到了一题支配树的题只能干瞪眼，书到用时方恨少呀。

推荐几篇博客：https://blog.csdn.net/a710128/article/details/49913553

https://blog.csdn.net/litble/article/details/83019578

把图分为树，DAG，有向图三类有不同的求支配树的办法。重点是求一般有向图的办法，这个算法十分巧妙一看是Tarjan大神发明的，那没事了qaq。

树：显然树本身就是一棵支配树，不用求。

DAG：因为没有环的关系，DAG的访问先后顺序是十分显然的，所以DAG的支配树求解也要比普通有向图要简单：按照拓扑序从小到大进行，假设处理到点x，则查一遍所有可达点x的点y，所有点y一定被加入了支配树中，那么它们在支配树上的LCA就是x在支配树上的父亲。(来自litble大佬原话)

洛谷P2597 灾难

差不多就是DAG上的支配树裸题，求DAG每个点能支配的点数。用上诉求法+倍增求LCA可解。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,t,num,rev[N],dep[N],ans[N];
vector<int> G[N],rG[N],dom[N];

queue<int> q;
int f[N][20],indeg[N],deg[N];
void toposort() {
    for (int i=1;i<=n;i++)
        if (indeg[i]==0) G[0].push_back(i),rG[i].push_back(0),indeg[i]++;
    q.push(0); num=0;
    while (!q.empty()) {
        int x=q.front(); q.pop();
        rev[++num]=x;
        for (int i=0;i<G[x].size();i++)
            if (--indeg[G[x][i]]==0) q.push(G[x][i]);
    }    
}

int LCA(int x,int y) {
    if (dep[x]<dep[y]) swap(x,y);
    for (int i=t;i>=0;i--)
        if (dep[f[x][i]]>=dep[y]) x=f[x][i];
    if (x==y) return x;
    for (int i=t;i>=0;i--)
        if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];        
}

void getans(int x) {
    ans[x]=1;
    for (int i=0;i<dom[x].size();i++) {
        getans(dom[x][i]);
        ans[x]+=ans[dom[x][i]];
    }
}

int main()
{
    scanf("%d",&n);
    t=(int)log2(n)+1;
    for (int i=1;i<=n;i++) {
        int x; 
        while (scanf("%d",&x) && x) {
            G[x].push_back(i); rG[i].push_back(x);
            indeg[i]++;
        }
    }
    toposort();  //得到拓扑序 
    for (int i=2;i<=n+1;i++) {  //按照拓扑序进行构建支配树 
        int x=rev[i],y=rG[x][0];
        for (int j=1;j<rG[x].size();j++) y=LCA(y,rG[x][j]);  //到达x的所有点的LCA 
        dom[y].push_back(x); dep[x]=dep[y]+1; f[x][0]=y;
        for (int j=1;j<=15;j++) f[x][j]=f[f[x][j-1]][j-1];
    }
    
    getans(0);
    for (int i=1;i<=n;i++) printf("%d
",ans[i]-1);
    return 0;
}

当然也可以用下面的一般有向图的办法来求支配树。这题注意加个超级源点0指向所以的入度为0的点。为什么非要加超级源点而不能每个入度为0的点都作为起点跑一遍呢？因为有可能两个入度为0的点指向同一个点就会出问题。主要原因就是并不是入度为0的点不连通。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 3e5+10;
int n,dfs_clock,dfn[N],rev[N],f[N],indeg[N];  //点的dfs序，dfs对应的点，父亲结点 
int semi[N],idom[N],Ans[N];  //半支配点，支配点 

struct Node{int to,next;};
struct Graph{  //树 
  int tot,head[N];
  Node E[N]; 
  inline void clear() {
    tot=0;
    for(int i=0;i<=n;++i) head[i]=0;
  }
  inline void link(int u,int v) {
    E[++tot]=(Node){v,head[u]}; head[u]=tot;
  }
}pre,nxt,dom;  //nxt原树，pre反树，dom支配树 

struct uset{  //并查集 
  int fa[N],Mi[N];
  inline void init() {
    for(int i=1;i<=n;++i)
      fa[i]=Mi[i]=semi[i]=i;
  }
  inline int find(int x){
    if(fa[x]==x)return x;
    int fx=fa[x],y=find(fa[x]);
    if(dfn[semi[Mi[fx]]]<dfn[semi[Mi[x]]])Mi[x]=Mi[fx];
    return fa[x]=y;
  }
}uset;

inline void dfs(int x) {  //先dfs一遍计算dfn,rev,father数组 
  dfn[x]=++dfs_clock;rev[dfs_clock]=x;
  for(int e=nxt.head[x];e;e=nxt.E[e].next){
    if(!dfn[nxt.E[e].to])
      f[nxt.E[e].to]=x,dfs(nxt.E[e].to);
  }
}

inline void getans(int x) {  //计算答案，每个点被多少个点支配 
  Ans[x]=1;
  for(int e=dom.head[x];e;e=dom.E[e].next) {
      getans(dom.E[e].to);
      Ans[x]+=Ans[dom.E[e].to];
  } 
}

inline void calc() {  //构建支配树 
  for(int i=n+1;i>=2;--i) {  //从dfs序大的点开始 
    int y=rev[i],tmp=n;
    for(int e=pre.head[y];e;e=pre.E[e].next) {  //所有能到达y点的边 
      int x=pre.E[e].to;  // (x,y) 
      //if (!dfn[x]) continue;
      if (dfn[x]<dfn[y]) tmp=min(tmp,dfn[x]);
      else uset.find(x),tmp=min(tmp,dfn[semi[uset.Mi[x]]]);
    }
    semi[y]=rev[tmp];uset.fa[y]=f[y];
    dom.link(semi[y],y);
    
    y=rev[i-1];
    for (int e=dom.head[y];e;e=dom.E[e].next) {
      int x=dom.E[e].to; uset.find(x);
      if (semi[uset.Mi[x]]==y) idom[x]=y;
      else idom[x]=uset.Mi[x];
    }
  }

  for(int i=2;i<=n+1;++i){
    int x=rev[i];
    if(idom[x]!=semi[x]) idom[x]=idom[idom[x]];
  }
  
  dom.clear();
  for(int i=1;i<=n;++i) dom.link(idom[i],i);
    
  getans(0);  //计算答案 
  for(int i=1;i<=n;++i) {
    printf("%d",Ans[i]-1),Ans[i]=0;
    printf("
");
  }
}

int main() {
  scanf("%d",&n);
      dfs_clock=0; pre.clear(); nxt.clear(); dom.clear();
      for(int i=1;i<=n;++i) dfn[i]=rev[i]=semi[i]=idom[i]=f[i]=0;
    for (int i=1;i<=n;i++) {
        int x; 
        while (scanf("%d",&x) && x) {
            nxt.link(x,i); pre.link(i,x);
            indeg[i]++;
        }
    }
    
    for (int i=1;i<=n;i++)
        if (indeg[i]==0) nxt.link(0,i),pre.link(i,0);
    dfs(0);
    uset.init();
    calc();
  return 0;
}

一般有向图：简单来说就是利用dfs序求出半支配点，然后修正半支配点得到支配点父亲结点，连接支配父亲点到点的边得到支配树。建议看上面两位大佬的博客，说得十分清楚了。(甚至ICPC选手都不需要完全搞懂细节)。这里直接给出抄袭的上诉大佬的模板代码(加了点注释)。

洛谷P5180  支配树模板题

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 3e5+10;
int n,m,dfs_clock,dfn[N],rev[N],f[N];  //点的dfs序，dfs对应的点，父亲结点 
int semi[N],idom[N],Ans[N];  //半支配点，支配点 

struct Node{int to,next;};
struct Graph{  //树 
  int tot,head[N];
  Node E[N]; 
  inline void clear() {
    tot=0;
    for(int i=0;i<=n;++i) head[i]=0;
  }
  inline void link(int u,int v) {
    E[++tot]=(Node){v,head[u]}; head[u]=tot;
  }
}pre,nxt,dom;  //nxt原树，pre反树，dom支配树 

struct uset{  //并查集 
  int fa[N],Mi[N];
  inline void init() {
    for(int i=1;i<=n;++i)
      fa[i]=Mi[i]=semi[i]=i;
  }
  inline int find(int x){
    if(fa[x]==x)return x;
    int fx=fa[x],y=find(fa[x]);
    if(dfn[semi[Mi[fx]]]<dfn[semi[Mi[x]]])Mi[x]=Mi[fx];
    return fa[x]=y;
  }
}uset;

inline void dfs(int x) {  //先dfs一遍计算dfn,rev,father数组 
  dfn[x]=++dfs_clock;rev[dfs_clock]=x;
  for(int e=nxt.head[x];e;e=nxt.E[e].next){
    if(!dfn[nxt.E[e].to])
      f[nxt.E[e].to]=x,dfs(nxt.E[e].to);
  }
}

inline void getans(int x) {  //计算答案，每个点被多少个点支配 
  Ans[x]=1;
  for(int e=dom.head[x];e;e=dom.E[e].next) {
      getans(dom.E[e].to);
      Ans[x]+=Ans[dom.E[e].to];
  } 
}

inline void calc() {  //构建支配树 
  for(int i=n;i>=2;--i) {  //从dfs序大的点开始 
    int y=rev[i],tmp=n;
    for(int e=pre.head[y];e;e=pre.E[e].next) {  //所有能到达y点的边 
      int x=pre.E[e].to;  // (x,y) 
      if (!dfn[x]) continue;
      if (dfn[x]<dfn[y]) tmp=min(tmp,dfn[x]);
      else uset.find(x),tmp=min(tmp,dfn[semi[uset.Mi[x]]]);
    }
    semi[y]=rev[tmp];uset.fa[y]=f[y];
    dom.link(semi[y],y);
    
    y=rev[i-1];
    for (int e=dom.head[y];e;e=dom.E[e].next) {
      int x=dom.E[e].to; uset.find(x);
      if (semi[uset.Mi[x]]==y) idom[x]=y;
      else idom[x]=uset.Mi[x];
    }
  }

  for(int i=2;i<=n;++i){
    int x=rev[i];
    if(idom[x]!=semi[x]) idom[x]=idom[idom[x]];
  }
  
  dom.clear();
  for(int i=2;i<=n;++i) dom.link(idom[i],i);  //2-n点连接支配树 
    
  getans(1);  //计算答案 
  for(int i=1;i<=n;++i) {
    printf("%d",Ans[i]),Ans[i]=0;
    i==n?printf("
"):printf(" ");
  }
}

//P5180支配树模板  起点为1的有向图  求每个点能支配的点的个数（包括自己）
int main() {
  scanf("%d%d",&n,&m);
      dfs_clock=0; pre.clear(); nxt.clear(); dom.clear();
      for(int i=1;i<=n;++i) dfn[i]=rev[i]=semi[i]=idom[i]=f[i]=0;
    for(int i=1;i<=m;++i) {
      int u,v; scanf("%d%d",&u,&v);
      nxt.link(u,v);
      pre.link(v,u);
    }
    dfs(1);
    uset.init();
    calc();
  return 0;
}

HDU-4694

支配树裸题：给出有向图 求能支配每个点的点数量 。直接求出支配树然后统计答案。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 200010;
int n,m,dfs_clock,dfn[N],rev[N],f[N];  //点的dfs序，dfs对应的点，父亲结点 
int semi[N],idom[N],Ans[N];  //半支配点，支配点 

struct Node{int to,next;};
struct Graph{  //树 
  int tot,head[N];
  Node E[N]; 
  inline void clear() {
    tot=0;
    for(int i=0;i<=n;++i) head[i]=0;
  }
  inline void link(int u,int v) {
    E[++tot]=(Node){v,head[u]}; head[u]=tot;
  }
}pre,nxt,dom;  //nxt原树，pre反树，dom支配树 

struct uset{  //并查集 
  int fa[N],Mi[N];
  inline void init() {
    for(int i=1;i<=n;++i)
      fa[i]=Mi[i]=semi[i]=i;
  }
  inline int find(int x){
    if(fa[x]==x)return x;
    int fx=fa[x],y=find(fa[x]);
    if(dfn[semi[Mi[fx]]]<dfn[semi[Mi[x]]])Mi[x]=Mi[fx];
    return fa[x]=y;
  }
}uset;

inline void dfs(int x) {  //先dfs一遍计算dfn,rev,father数组 
  dfn[x]=++dfs_clock;rev[dfs_clock]=x;
  for(int e=nxt.head[x];e;e=nxt.E[e].next){
    if(!dfn[nxt.E[e].to])
      f[nxt.E[e].to]=x,dfs(nxt.E[e].to);
  }
}

inline void getans(int x,int sum) {  //计算答案，每个点被多少个点支配 
  Ans[x]=sum+x;
  for(int e=dom.head[x];e;e=dom.E[e].next)
    getans(dom.E[e].to,sum+x);
}

inline void calc() {  //构建支配树 
  for(int i=n;i>=2;--i) {  //从dfs序大的点开始 
    int y=rev[i],tmp=n;
    for(int e=pre.head[y];e;e=pre.E[e].next) {  //所有能到达y点的边 
      int x=pre.E[e].to;  // (x,y) 
      if (!dfn[x]) continue;
      if (dfn[x]<dfn[y]) tmp=min(tmp,dfn[x]);
      else uset.find(x),tmp=min(tmp,dfn[semi[uset.Mi[x]]]);
    }
    semi[y]=rev[tmp];uset.fa[y]=f[y];
    dom.link(semi[y],y);
    
    y=rev[i-1];
    for (int e=dom.head[y];e;e=dom.E[e].next) {
      int x=dom.E[e].to; uset.find(x);
      if (semi[uset.Mi[x]]==y) idom[x]=y;
      else idom[x]=uset.Mi[x];
    }
  }

  for(int i=2;i<=n;++i){
    int x=rev[i];
    if(idom[x]!=semi[x]) idom[x]=idom[idom[x]];
  }
  
  dom.clear();
  for(int i=1;i<n;++i) dom.link(idom[i],i);
    
  getans(n,0);  //计算答案 
  for(int i=1;i<=n;++i){
    printf("%d",Ans[i]),Ans[i]=0;
    i==n?printf("
"):printf(" ");
  }
}

//HDU-4694 给出有向图 求能支配每个点的点数量 
int main() {
  while(scanf("%d%d",&n,&m)==2) {
      dfs_clock=0; pre.clear(); nxt.clear(); dom.clear();
      for(int i=1;i<=n;++i) dfn[i]=rev[i]=semi[i]=idom[i]=f[i]=0;
    for(int i=1;i<=m;++i) {
      int u,v; scanf("%d%d",&u,&v);
      nxt.link(u,v);
      pre.link(v,u);
    }
    dfs(n);
    uset.init();
    calc();
  }
  return 0;
}

题目练习：

HDU-6604

多校的一道题。比赛的时候还没学支配树想了半天。后来才知道是支配树，学了之后感觉这题其实不难。

题意：给一个n个点m条边的DAG，每次询问给出两个点x,y，问删除DAG的某一个点可以使得 至少xy中的某一个点不能走到任何一个叶子结点，问删除的方案数。

解法：不能走到任何一个叶子结点，想到什么了？也就是要删除的这个点说是所有叶子结点到x/y的必经点，也就是叶子结点支配着x/y（当然也可以说x/y支配着叶子，但是此题我们处理询问时候叶子是不变的东西，所有我们要把叶子当成根）。于是我们考虑反向建图，把叶子当成根(当然因为有多个叶子要加超级源点)构建支配树。根据支配树的定义，那么答案明显就是dep[x]+dep[y]-dep[LCA(x,y)]（减去重复部分），此题可解了。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m,t,num,rev[N],dep[N];
vector<int> G[N],rG[N],dom[N];

queue<int> q;
int f[N][20],indeg[N];
void toposort() {
    for (int i=1;i<=n;i++)
        if (indeg[i]==0) G[0].push_back(i),rG[i].push_back(0),indeg[i]++;
    q.push(0); num=0;
    while (!q.empty()) {
        int x=q.front(); q.pop();
        rev[++num]=x;
        for (int i=0;i<G[x].size();i++)
            if (--indeg[G[x][i]]==0) q.push(G[x][i]);
    }    
}

int LCA(int x,int y) {
    if (dep[x]<dep[y]) swap(x,y);
    for (int i=t;i>=0;i--)
        if (dep[f[x][i]]>=dep[y]) x=f[x][i];
    if (x==y) return x;
    for (int i=t;i>=0;i--)
        if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];        
}

int main()
{
    int T; cin>>T;
    while (T--) {
        scanf("%d%d",&n,&m);
        for (int i=0;i<=n;i++) G[i].clear(),rG[i].clear(),dom[i].clear();
        num=0; for (int i=0;i<=n;i++) dep[i]=rev[i]=indeg[i]=0;
        t=(int)log2(n)+1;
        for (int i=1;i<=m;i++) {
            int x,y; scanf("%d%d",&x,&y);
            rG[x].push_back(y); G[y].push_back(x); indeg[x]++;
        }
        toposort();  //得到拓扑序 
        for (int i=2;i<=n+1;i++) {  //按照拓扑序进行构建支配树 
            int x=rev[i],y=rG[x][0];
            for (int j=1;j<rG[x].size();j++) y=LCA(y,rG[x][j]);  //到达x的所有点的LCA 
            dom[y].push_back(x); dep[x]=dep[y]+1; f[x][0]=y;
            for (int j=1;j<=t;j++) f[x][j]=f[f[x][j-1]][j-1];
        }
        
        int Q; scanf("%d",&Q);
        for (int i=1;i<=Q;i++) {
            int x,y; scanf("%d%d",&x,&y);
            int lca=LCA(x,y);
            int ans=dep[x]+dep[y]-dep[lca];
            printf("%d
",ans);
        }
    }
    return 0;
}