题解 P5180 【【模板】支配树】

hezlik · 2020-08-16 20:27:53 · 题解

前言.

写这篇文章主要是因为大部分题解里要么代码实现的时候时间复杂度是假的，要么只是求解半支配点后直接用 DAG 上树上倍增的方法做，这里想写一份复杂度正确的题解与代码。

由于本人水平有限，这里只是大概介绍怎么做，不介绍如何证明。

支配树概念.

对于一张有向图，我们确定一个起点 S。

对于一个点 k，称 x 为其支配点当且仅当，删去点 x 后，S 无法到达 k，即 S 到达 k 的所有路径都必须通过 x。

容易发现，一个点的支配点不止一个。

同时，也很容易发现，如果我们将一个点 k 与其最近的支配点连边，那么会形成一个树形结构，这个树形结构即支配树。

接下来我们所称的支配点一般指其在支配树上的父亲。

求解支配树的一个优秀做法是 Lengauer-Tarjan 算法，可以做到在 O(n\alpha(n)) 或 O(n\log n) 的时间复杂度内求解支配树。

DAG 上的支配树构造 .

虽然这部分与 Lengauer-Tarjan 算法并没有什么关系，不过还是介绍一下吧。

首先，显然一个点 k 的支配点是所有能够直接到达 k 的点在支配树上的 LCA。

那么就很简单了，我们按照拓扑序依次做下去，建立反图找到所有能够直接到达当前点的点，倍增求解 LCA 即可。

Lengauer-Tarjan 算法

Lengauer-Tarjan 算法的分为三步：

求出 dfs 树，得到每个点 k 的 dfs 序 d_k。
求解半支配点。
求解支配点。

引入半支配点.

Lengauer-Tarjan 算法的精髓在于引入了半支配点这个概念。

一个点 k 的半支配点是指一个 dfs 序最小的点 x，使得 x 可以通过一条路径 x,x_1,x_2,\cdots,x_c,k 到达点 k ，求满足对于任意 1\leq i\leq c，有 d_{x_i}>d_k。

只要能求出半支配点，就有办法求解支配点，所以我们先来求解半支配点。

对于一个可以直接到达点 k 的点 x，有两种可能的情况：

若 d_x<d_k，则 x 可能是 k 的半支配点。
若 d_x>d_k，则考虑其所有祖先 u 满足 d_u>d_k，u 的半支配点可能是点 k 的半支配点。

可以证明这两种情况是充分的。

考虑按照 dfs 序倒序考虑所有点 k。枚举所有能够直接到达点 k 的点 x，第一种情况可以快速维护，但第二种情况需要考虑其所有祖先，我们不能暴力枚举。

考虑维护一个带权并查集，每次处理完一个点 k，我们就将 k 往其 dfs 树上的父亲合并，同时维护一个点并查集中除根以外的所有祖先中，半支配点 dfs 序最小的那个点，就可以在一次 O(\log n) 的时间复杂度内完成第二种情况的查询。

至此，我们已经在 O(n\log n) 的时间复杂度内完成了半支配点的求解。

利用半支配点求解支配点.

考虑点 k 到其半支配点 x 的这条链（不包括 x）上半支配点 dfs 序最小的点 u 及其半支配点 v，则 k 在支配点有两种情况：

若 x=v，则 k 的支配点就是 x。
若 d_x>d_v，则 k 的支配点是 u 的支配点。

可以证明这两种情况是充分必要的。

我们再次考虑按照 dfs 序倒序处理。

对于一个点 k，我们考虑其在半支配点 x，现在需要完成在 dfs 树上查询 k 到 x 这条链（不包含 x）中半支配点 dfs 序最小的点。

我们发现这个查询就在半支配点的求解中出现过。

考虑在求解半支配点同时求解支配点。当我们求出 k 的半支配点后，将 k 的半支配点与 k 连边，维护半支配树。同时令 x 为 k 在 dfs 树上的父亲，枚举 x 在半支配树上的儿子 y，容易发现当前并查集中维护的正好就是 y 到 x（不包含 x）中半支配点 dfs 序最小的点。

不过一个问题是，如果查询出来的结果是第二种情况，此时我们并不知道得到点的支配点，所以把得到点先存下来，最后再按照 dfs 序正序处理一遍就好了。

同时，如果我们每一次都枚举 k 的父亲 x 在半支配树中的所有儿子，会导致多次枚举了某些点，所以每次枚举完之后需要将这些儿子清空才能保证复杂度正确。这也是大部分题解复杂度错误的原因。

至此，我们已经在 O(n\log n) 的时间复杂度内完成了支配点的求解，也就完成了整个 Lengauer-Tarjan 算法。

代码如下：

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

typedef long long LL;

const int N=200000,M=300000;

int n,m;
struct side{
  int y,next;
}e[M*2+N+9];
int lin[3][N+9],cs;
//0为原图，1为反图，2为半支配树

void Ins(int id,int x,int y){e[++cs].y=y;e[cs].next=lin[id][x];lin[id][x]=cs;}

void into(){
  scanf("%d%d",&n,&m);
  for (int i=1;i<=m;++i){
    int x,y;
    scanf("%d%d",&x,&y);
    Ins(0,x,y);Ins(1,y,x);
  }
}

int dfn[N+9],ord[N+9],co;
int fa[N+9];

void Tarjan(int k){
  ord[dfn[k]=++co]=k;
  for (int i=lin[0][k];i;i=e[i].next)
    if (!dfn[e[i].y]){
      fa[e[i].y]=k;
      Tarjan(e[i].y);
    }
}

int idom[N+9],sdom[N+9];
int uni[N+9],mn[N+9];

int Query_uni(int k){
  if (k==uni[k]) return k;
  int res=Query_uni(uni[k]);
  if (dfn[sdom[mn[uni[k]]]]<dfn[sdom[mn[k]]]) mn[k]=mn[uni[k]];
  return uni[k]=res;
}

void Contract(int st){
  Tarjan(st);
  for (int i=1;i<=n;++i) sdom[i]=uni[i]=mn[i]=i;
  for (int i=co;i>=2;--i){
    int t=ord[i];
    for (int i=lin[1][t];i;i=e[i].next){
      int y=e[i].y;
      if (!dfn[y]) continue;
      //如果无法到达y则直接跳过
      Query_uni(y);
      if (dfn[sdom[mn[y]]]<dfn[sdom[t]]) sdom[t]=sdom[mn[y]];
    }
    uni[t]=fa[t];
    //半支配点的求解过程
    Ins(2,sdom[t],t);
    //维护半支配树
    for (int i=lin[2][t=fa[t]];i;i=e[i].next){
      int y=e[i].y;
      Query_uni(y);
      idom[y]=t==sdom[mn[y]]?t:mn[y];
    }
    //支配点的求解过程
    lin[2][t]=0;
    //清空已扫过的儿子
  }
  for (int i=2;i<=co;++i){
    int t=ord[i];
    if (idom[t]^sdom[t]) idom[t]=idom[idom[t]];
  }
  //最后的正序扫描
}

int ans[N+9];

void Get_ans(){
  for (int i=co;i>=2;--i) ans[idom[ord[i]]]+=++ans[ord[i]];
  ++ans[1];
}

void work(){
  Contract(1);
  Get_ans();
}

void outo(){
  for (int i=1;i<=n;++i)
    printf("%d ",ans[i]);
  puts("");
}

int main(){
  into();
  work();
  outo();
  return 0;
}