首页 > 其他分享 >支配树

支配树

时间：2024-01-22 19:57:16浏览次数：24  
标签：sdom 支配 int rev dfn idom

Dominator Tree

被支配哩。自闭哩。。。

没有详细的证明。


Dominator

对于一个任意的有向图，我们钦定一个入口 \(s\)，对于任意一个节点 \(u\)，

如果从 \(s \to u\) 的任意路径都经过节点 \(v\)，称为 \(v\) 支配 \(u\)，\(v\) 也是 \(u\) 的一个支配点，记作 \(v \ dom \ u\)。


容易发现，支配关系具有传递性，自反性和反对称性。

  • 若 \(v \ dom \ u\) 且 \(u \ dom \ w\)，那么 \(v \ dom \ w\)。
  • 若 \(u \ dom \ v\) 且 \(v \ dom \ u\)，那么 \(u=v\)。
  • \(u \ dom \ u\)。

支配满足偏序关系，若直接建图只能得到一个 DAG，不够优秀，所以我们考虑另一种方法。


Tree

在 \(u\) 的支配点中，我们找到除了 \(u\) 的距离 \(u\) 最近的一个点 \(v\)，把 \(v\) 称为 \(u\) 的 直接支配点，记作 \(v \ idom \ u\)。

我们将 \(idom_u\) 向 \(u\) 连边，发现容易得到一棵树，

这棵树就叫做 支配树，

而对于一个节点 \(u\) 它的支配点就是它的祖先。


如何求这棵树呢？

我们需要引入 半支配点 这一概念，利用半支配点求解支配点。


首先我们从起点跑一次 dfs，求出了每一个点的 \(dfn\) 序。

那么一个点 \(u\) 的半支配点 \(v\) 满足从 \(v\) 出发存在一条路径 \(v \to v_1 \to v_2 \to \dots \to v_k \to u\) 满足 \(\forall i\in[1,k],dfn_{v_i} \gt dfn_u\)，

其中 \(v\) 是满足条件的 \(dfn\) 序最小的那一个，记作 \(v \ sdom \ u\)。


而这个半支配点会有许多性质：

  • \(sdom_u\) 是 \(u\) 的祖先。

    感觉挺显然的。因为如果不是，那么 \(fa(sdom_u)\) 也可以成为半支配点，与定义矛盾。

  • \(idom_u\) 是 \(sdom_u\) 的祖先。

    如果不是，那么就存在一条路径不经过 \(idom_u\) 了，与定义矛盾。

如何求解半支配点？

发现其实一个点的半支配点就是 dfn 比他大且能到他的点的到其祖先路径上的半支配点最小的一个。

可以尝试画图理解，感觉感性理解还是好的，不会理性证明。


这样我们可以求得半支配点，现在考虑如何求支配点呢？

我们就需要用到半支配点的两个定理：

  • 对于一个点 \(u\)，若 dfs 树上从 \(sdom_u\) 到 \(w\) 的路径上任意节点 \(v\) 满足 \(sdom_v \ge sdom_u\)，那么 \(idom_u =sdom_u\)。
  • 对于一个点 \(u\)，从 \(sdom_u\) 到 \(u\) 的路径上所有节点半支配点最小的那个点是 \(u\)，满足 \(sdom_v \le sdom_u\) 且 \(idom_v = idom_u\)。

这里需要强大的感性理解，感受那股劲你就懂了。

感觉不如看代码。


于是这个样子我们用并查集维护一个点到祖先路径上的半支配点的最小值，

按照 dfs 序倒叙枚举即可。

时间复杂度是 \(\mathcal O(n \log n)\)，这样我们就做完了。


放上一个板子。封装过了！

namespace DT{
  int n,idx=0,dfn[N],rev[N],fa[N],f[N],mn[N],idom[N],sdom[N];
  vector<int> e[N],ie[N],tr[N];
  void add(int u,int v){e[u].pb(v);ie[v].pb(u);}
  void init(int _n){
    n=_n;idx=0;
    for(int i=1;i<=n;i++){
      f[i]=sdom[i]=mn[i]=i;
      dfn[i]=rev[i]=idom[i]=fa[i]=0;
      e[i].clear(),ie[i].clear(),tr[i].clear();
    }
  }
  void dfsp(int u){
    dfn[u]=++idx;rev[idx]=u;
    for(auto v:e[u]) if(!dfn[v]) fa[v]=u,dfsp(v);
  }
  int find(int x){
    if(x==f[x]) return x;
    int nw=find(f[x]);
    if(dfn[sdom[mn[f[x]]]]<dfn[sdom[mn[x]]]) mn[x]=mn[f[x]];
    return f[x]=nw;
  }
  void build(int rt){
    dfsp(rt);
    for(int i=n,u;i>1;i--){
      u=rev[i];
      for(auto v:ie[u]){
        find(v);
        if(dfn[sdom[mn[v]]]<dfn[sdom[u]]) sdom[u]=sdom[mn[v]];
      }
      f[u]=fa[u];
      tr[sdom[u]].pb(u);
      u=fa[u];
      for(auto v:tr[u]) find(v),idom[v]=(u==sdom[mn[v]])?u:mn[v];
      tr[u].clear();
    }
    for(int i=2;i<=n;i++) if(idom[rev[i]]!=sdom[rev[i]]) idom[rev[i]]=idom[idom[rev[i]]];
  }
  void getans(){
    for(int i=n;i>=2;i--) ans[idom[rev[i]]]+=++ans[rev[i]];
    ++ans[1];  
  }
}

支配树还是非常好看的呢！感觉建出树来性质就非常优美啊。。。


Exercise

一些题目，里面也有我学习支配树的来源——恶心的联考啊。


P5180 【模板】支配树

P5180 【模板】支配树

很板了吧。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back

const int N=2e5+5;
int n,m,ans[N];

namespace DT{
  int n,idx=0,dfn[N],rev[N],fa[N],f[N],mn[N],idom[N],sdom[N];
  vector<int> e[N],ie[N],tr[N];
  void add(int u,int v){e[u].pb(v);ie[v].pb(u);}
  void init(int _n){
    n=_n;idx=0;
    for(int i=1;i<=n;i++){
      f[i]=sdom[i]=mn[i]=i;
      dfn[i]=rev[i]=idom[i]=fa[i]=0;
      e[i].clear(),ie[i].clear(),tr[i].clear();
    }
  }
  void dfsp(int u){
    dfn[u]=++idx;rev[idx]=u;
    for(auto v:e[u]) if(!dfn[v]) fa[v]=u,dfsp(v);
  }
  int find(int x){
    if(x==f[x]) return x;
    int nw=find(f[x]);
    if(dfn[sdom[mn[f[x]]]]<dfn[sdom[mn[x]]]) mn[x]=mn[f[x]];
    return f[x]=nw;
  }
  void build(int rt){
    dfsp(rt);
    for(int i=n,u;i>1;i--){
      u=rev[i];
      for(auto v:ie[u]){
        find(v);
        if(dfn[sdom[mn[v]]]<dfn[sdom[u]]) sdom[u]=sdom[mn[v]];
      }
      f[u]=fa[u];
      tr[sdom[u]].pb(u);
      u=fa[u];
      for(auto v:tr[u]) find(v),idom[v]=(u==sdom[mn[v]])?u:mn[v];
      tr[u].clear();
    }
    for(int i=2;i<=n;i++) if(idom[rev[i]]!=sdom[rev[i]]) idom[rev[i]]=idom[idom[rev[i]]];
  }
  void getans(){
    for(int i=n;i>=2;i--) ans[idom[rev[i]]]+=++ans[rev[i]];
    ++ans[1];  
  }
}

int main(){
  /*2024.1.22 H_W_Y P5180 【模板】支配树 dominator tree*/ 
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin>>n>>m;DT::init(n);
  for(int i=1,u,v;i<=m;i++) cin>>u>>v,DT::add(u,v);
  DT::build(1);
  DT::getans();
  for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
  return 0;
}

P2597 [ZJOI2012] 灾难

P2597 [ZJOI2012] 灾难)

支配树的起源，依旧很板。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back

const int N=2e5+5;
int n,m,ans[N],rt[N],cnt=0;

namespace DT{
  int n,idx=0,dfn[N],rev[N],f[N],fa[N],idom[N],sdom[N],mn[N];
  vector<int> e[N],ie[N],tr[N];
  void add(int u,int v){e[u].pb(v),ie[v].pb(u);}
  void init(int _n){
    n=_n;idx=0;
    for(int i=1;i<=n;i++){
      f[i]=sdom[i]=mn[i]=i;
      dfn[i]=rev[i]=idom[i]=fa[i]=0;
      e[i].clear(),ie[i].clear(),tr[i].clear();
    } 
  }
  void dfsp(int u){
    dfn[u]=++idx;rev[idx]=u;
    for(auto v:e[u]) if(!dfn[v]) fa[v]=u,dfsp(v);
  }
  int find(int x){
    if(f[x]==x) return x;
    int nw=find(f[x]);
    if(dfn[sdom[mn[f[x]]]]<dfn[sdom[mn[x]]]) mn[x]=mn[f[x]];
    return f[x]=nw;
  }
  void build(int rt){
    int lst=idx+1;
    dfsp(rt);
    for(int i=idx,u;i>lst;i--){
      u=rev[i];
      for(auto v:ie[u]){
        find(v);
        if(dfn[sdom[mn[v]]]<dfn[sdom[u]]) sdom[u]=sdom[mn[v]];
      }
      f[u]=fa[u];
      tr[sdom[u]].pb(u);
      u=fa[u];
      for(auto v:tr[u]) find(v),idom[v]=(u==sdom[mn[v]])?u:mn[v];
      tr[u].clear();
    }
    for(int i=lst+1;i<=idx;i++) if(idom[rev[i]]!=sdom[rev[i]]) idom[rev[i]]=idom[idom[rev[i]]];
    for(int i=idx;i>lst;i--) ans[idom[rev[i]]]+=++ans[rev[i]];
    ans[rev[lst]]++;
  }
} 

int main(){
  /*2024.1.22 H_W_Y P2597 [ZJOI2012] 灾难 支配树*/ 
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin>>n;DT::init(n);
  for(int i=1,x;i<=n;i++){
    cin>>x;
    if(x==0) rt[++cnt]=i;
    while(x) DT::add(x,i),cin>>x;
  }
  for(int i=1;i<=cnt;i++) DT::build(rt[i]);
  for(int i=1;i<=n;i++) cout<<ans[i]-1<<'\n';
  return 0;
}

CF Gym 103860 - H(CCPC Finals 2021)

Problem - H - Codeforces

还记得那个冬日周六的傍晚，在 cdqz 504 机房，有三个人收到了一条神秘通知（是谁我不说）。

image

不仅如此，他们还收到了一条鼓励：

image

于是有个人，打开了 codeforces.com/gyms，把 Page 2 - 9 的比赛翻完了一遍，

没有找到很满意的题目，而这些不满意的题目中，这道题是最好的了，虽然考得有点偏，但是个人感觉挺有意思的。

由于只有一天的时间，于是搬题人迅速学习了 支配树，

赶着时间线终于完成了任务。而搬题人也因此被支配树支配了整整两天。/fn/fn/fn


求给定的⼆分图中有多少个点对满⾜删掉这两个点后最⼤匹配数不变。

\(1 \le n,m \le 2 \times 10^5\)。

很妙的一道题，在自己写完题解完全领悟之后倍感快乐。


首先去跑一次二分图最大匹配，在残图上面做是一定不劣的。

观察残图，如何才能在不改变流量的情况下删去一个点呢？

发现与 \(S\) 相连的点和与 \(T\) 相连的点是相互独立的，所以我们可以分开考虑，以与 \(S\) 相连的点 \(u\) 为例：

  • 当边 \((S,u)\) 残余容量 \(\gt 0\)，则直接删去边 \((S,u)\)。
  • 当边 \((S,u)\) 残余容量 \(=0\)，那么需要先找到一条包含 \((u,S)\) 的增广路径，让 \((S,u)\) 恢复容量，再删去。

容易发现，左侧点 \(u\) 能被删除等价于存在一条从 \(S\) 到 \((S,u)\) 或 \((u,S)\) 的增广路，具体实现过程中，为了方便，我们将边 \((S,u)\) 拆成 \((S,u')\) 和 \((u',u)\)，于是就只需要判断是否存在一条从 \(S\) 到虚点 \(u'\) 的增广路。

同理右侧点我们就从 \(T\) 出发，判断是否有到虚点的增广路即可。


现在回到题目中的两种情况：

  1. 异侧点：由于残图的两侧是相互独立的，那么我们只要求出 \(S\) 能到达的左侧点个数和 \(T\) 能到达的右侧点的个数，乘起来就是异侧点的方案数。

  2. 同侧点：以左侧点 \(u,v\) 为例，是否可以从 \(S\) 到 \(u'\) 和 \(v'\) 分别进行一次增广等价于是否存在两条没有公共路径的 \((S,u')\) 和 \((S,v')\)。于是我们可以对于每一条边都进行拆点，并以 \(S\) 为起点求支配树，存在这样的两条路径当且仅当 这两个虚点再支配树上的左右公共祖先均不是拆边的虚点，所以这样的方案数只需要再支配树上面统计即可。

    因为如果他们的支配点是虚点，那么这两个点就一定有相同的增广路，于是就一定不满足条件了。


具体实现时，可以直接把连向汇点的边反向连到原点上面，这样就只用跑一次支配树。

计数的时候直接在支配树上面 dfs，记录一下子树的虚点个数即可，代码好懂一些。

总时间复杂度 \(\mathcal O(m\sqrt n+ m\log m)\)。


支配树帮我们解决了找到两条路径他们没有公共点的方案数——非常强大。

令人感叹。

实现时我们如果把所有边拆了跑网络流需要卡常，

所以建议在跑完网络流之后再拆边，这样就可以轻松通过。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long

const int N=1e6+5;
int n,m,S,T,L[N],R[N],lc=0,rc=0,c,c1,c2;
ll res=0;
bool vis[N];
vector<int> g[N],G[N];

namespace DT{//Dominator Tree
  int n,idx=0,dfn[N],rev[N],f[N],fa[N],mn[N],idom[N],sdom[N];
  vector<int> e[N],ie[N],tr[N];
  void add(int u,int v){e[u].pb(v),ie[v].pb(u);}
  void init(int _n){
    n=_n;idx=0;
    for(int i=1;i<=n;i++){
      f[i]=sdom[i]=mn[i]=i;
      fa[i]=rev[i]=dfn[i]=idom[i]=0;
      e[i].clear(),ie[i].clear(),tr[i].clear();
    }
  }
  void dfsp(int u){
    dfn[u]=++idx;rev[idx]=u;
    for(auto v:e[u]) if(!dfn[v]) fa[v]=u,dfsp(v);
  }
  int find(int x){
    if(f[x]==x) return x;
    int nw=find(f[x]);
    if(dfn[sdom[mn[f[x]]]]<dfn[sdom[mn[x]]]) mn[x]=mn[f[x]];
    return f[x]=nw;
  }
  void build(int rt){
    dfsp(rt);
    for(int i=n,u;i>1;i--){
      u=rev[i];
      for(auto v:ie[u]){
        find(v);
        if(dfn[sdom[mn[v]]]<dfn[sdom[u]]) sdom[u]=sdom[mn[v]];
      }
      f[u]=fa[u];
      tr[sdom[u]].pb(u);
      u=fa[u];
      for(auto v:tr[u]) find(v),idom[v]=(u==sdom[mn[v]])?u:mn[v];
      tr[u].clear();
    }
    for(int i=2;i<=n;i++) if(idom[rev[i]]!=sdom[rev[i]]) idom[rev[i]]=idom[idom[rev[i]]];
  }
} 

struct MF{//Max Flow
  const int inf=1e9;
  int n,tot=1,head[N],lv[N],cur[N],S,T,ans;
  struct edge{int v,nxt,w;}e[N<<1];
  void init(){n=S=T=0,tot=1,memset(head,0,sizeof(head));}
  void add(int u,int v,int w){
    e[++tot]=(edge){v,head[u],w};head[u]=tot;
    e[++tot]=(edge){u,head[v],w^1};head[v]=tot; 
  }
  bool bfs(){
    memset(lv,-1,sizeof(lv));
    queue<int> Q;Q.push(S),lv[S]=1,cur[S]=head[S];
    while(!Q.empty()){
      int u=Q.front();Q.pop();
      for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].v,w=e[i].w;
        if(w&&lv[v]==-1) lv[v]=lv[u]+1,cur[v]=head[v],Q.push(v);
      }
    }
    return lv[T]!=-1;
  }
  int dfs(int u,int flow){
    if(!flow||u==T) return flow;
    int res=flow;
    for(int i=cur[u];i;i=e[i].nxt){
      cur[u]=i;int v=e[i].v,w=e[i].w;
      if(w&&lv[v]==lv[u]+1){
        int c=dfs(v,min(res,w));
        res-=c,e[i].w-=c,e[i^1].w+=c;
      }
      if(!res) break;
    } 
    return flow-res;
  }
  void Dinic(int _S,int _T){
    S=_S,T=_T;ans=0;
    while(bfs()) ans+=dfs(S,inf);
  }
}G1,G2;

void dfscol(int u,int col){
  !col?L[++lc]=u:R[++rc]=u;vis[u]=true;
  for(auto v:g[u]) if(!vis[v]) dfscol(v,col^1); 
}

int dfs(int u,int t){
  int sz=0;t&=(u<=c);
  for(auto v:G[u]){
    int nw=dfs(v,t);sz+=nw;
    if(t) res-=1ll*nw*nw;
  }
  if(t) res+=1ll*sz*sz;
  return sz+(u>c&&u<=c1);
}

int main(){
//  freopen("gentle.in","r",stdin);
//  freopen("gentle.out","w",stdout);
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  cin>>n>>m;res=0;S=n+1,T=c=n+2; 
  for(int i=1,u,v;i<=m;i++) cin>>u>>v,g[u].pb(v),g[v].pb(u); 
  for(int i=1;i<=n;i++) if(!vis[i]) dfscol(i,0);
  
  G1.init();G2.init();
  for(int i=1;i<=lc;i++) G1.add(S,L[i],1);
  for(int i=1;i<=rc;i++) G1.add(R[i],T,1);
  for(int i=1;i<=lc;i++) for(auto x:g[L[i]]) G1.add(L[i],x,1); 
  G1.Dinic(S,T);
  
  c1=c;
  for(int i=G1.head[S];i;i=G1.e[i].nxt) G2.add(S,++c1,G1.e[i].w),G2.add(c1,G1.e[i].v,G1.e[i].w);
  for(int i=G1.head[T];i;i=G1.e[i].nxt) G2.add(G1.e[i].v,++c1,G1.e[i].w^1),G2.add(c1,T,G1.e[i].w^1);
  c2=c1;
  for(int u=1;u<=lc;u++) for(int i=G1.head[L[u]];i;i=G1.e[i].nxt) if(G1.e[i].v!=S) G2.add(L[u],++c2,G1.e[i].w),G2.add(c2,G1.e[i].v,G1.e[i].w);
  DT::init(c2);G2.S=S,G2.T=T;G2.bfs();
  
  for(int u=1;u<=c2;u++)
    for(int i=G2.head[u];i;i=G2.e[i].nxt){
      int v=G2.e[i].v,w=G2.e[i].w;G2.e[i].w^=1;
      if(w&&G2.lv[u]!=-1&&G2.lv[v]!=-1) DT::add(u,v);
    }
  swap(G2.S,G2.T);G2.bfs();
  for(int u=1;u<=c2;u++)
    for(int i=G2.head[u];i;i=G2.e[i].nxt){
      int v=G2.e[i].v,w=G2.e[i].w;
      if(w&&G2.lv[u]!=-1&&G2.lv[v]!=-1) DT::add(u,v);
    }
  DT::add(S,T);DT::build(S);
  for(int i=2;i<=DT::idx;i++) G[DT::idom[DT::rev[i]]].pb(DT::rev[i]);
  dfs(S,1);
  cout<<res/2<<'\n';
  return 0;
}

好题啊好题。


Conclusion

支配树可以帮我们解决询问有多少对点他们存在一条都到 \(S\) 的路径，两路径不相交。

标签：sdom,支配,int,rev,dfn,idom
From： https://www.cnblogs.com/hwy0622/p/17980837/dominator-tree

相关文章

  • GYM102596L Yosupo's Algorithm【分治，支配对】
    给定平面上\(2n\)个点，每个点有坐标\((x_i,y_i)\)，权值\(w_i\)及颜色\(c_i\)。所有点满足：若\(c_i=0\)，则\(x_i<0\)；若\(c_i=1\)，则\(x_i>0\)。\(q\)次查询，每次给定\(L_i,R_i\)，你需要选择两个点\(i,j\)满足如下条件：\(c_i=0,c_j=1\)。\(x_i<L,x_j>R\)或\(x_......
  • 你有被if-else支配过吗？看完这篇文章，你就知道该怎么做
    在日常工作中，如果让你碰到一大堆if-else嵌套的代码，你会怎么做？背景最近在给之前负责的项目做CR的时候，在项目代码中发现有大量的if-else判断语句，阅读起来非常的折磨人而且也不利于后期的维护扩展，比较容易出问题。当时我直接气血上涌，差点昏过去。缓过几分钟之后，把写这段代码的......
  • 支配树
    支配关系给定一张有向图，钦定一个入口\(s\),对于一个节点\(u\),若从\(s\)到\(u\)的每一条路径都经过某一个节点\(v\),则我们称\(v\)支配\(u\),记作$v,\text{dom},u$,注意对于\(s\)不能到达的结点，其支配关系是无意义的，因此我们默认\(s\)能到达图上的所有节点引......
  • 控制流图+支配树
    编译器优化记录（1）0.为啥要写这个记录我感觉自己平时整理自己想法的机会实在是太少了。即便是对于自己花了很多时间想、或是花了很多时间学的东西，同样如此。写编译器优化的阶段学了很多方法，也看到了很多人类智慧，我希望能从头梳理一下认识它们的过程，来更好地体悟。我身边有几位......
  • 「黑科技」支配树
    定义给定一张有向图与一个起点\(s\)，如果要去掉起点\(s\)到某个点\(v\)的中间的某个点\(u\)后无法到达，那么称点\(u\)支配点\(v\)，\(u\)是\(v\)的一个支配点最近支配点\((idom[u])\)\(u\)的支配点中距离\(u\)最近的一点支配树由所有边\(idom[u]\rightar......
  • MATLAB程序采用非支配排序遗传算法（NSGA2）求解分布式电源选址定容问题，可作为一个有用的
    MATLAB程序采用非支配排序遗传算法（NSGA2）求解分布式电源选址定容问题，可作为一个有用的参考，程序注释明确，算法原理可以自己搜。YID:4120651507678049......
  • MATLAB程序采用非支配排序遗传算法（NSGA2）求解分布式电源选址定容问题，可作为一个有用的
    MATLAB程序采用非支配排序遗传算法（NSGA2）求解分布式电源选址定容问题，可作为一个有用的参考，程序注释明确，算法原理可以自己搜。YID:4120651507678049......
  • luogu P7520 [省选联考 2021 A 卷] 支配
    题面传送门自己瞎胡的支配树，可能是错的（大雾首先我们可以证明，支配关系成树。考虑一个点\(x\)的两个受支配点\(y,z\)，这两个点应该在一条路径上，如果\(y,z\)之间没有支......
  • 【学习笔记】支配树
    先对自己说句话：你觉得没用的算法不一定没用，别太自以为是在那里一遍一遍叫"stoplearninguselessalgorithm"，最useless的是你。支配给定一个有向图\(G\)，有一个起点......
  • 基于matlab的最小支配集CDS仿真
    1.算法描述       支配集的定义如下：给定无向图G=（V,E）,其中V是点集，E是边集，称V的一个子集S称为支配集当且仅当对于V-S中任何一个点v,都有S中的某个点u,使得(u,......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99