【模板】支配树 题解

· · 题解

看了许多大佬的讲解，就用自己的语言说一遍，可能讲得不好（毕竟还是太菜了）

题目大医

给定一张有向图，求从起点出发，求所有点再去掉的情况下有多少个点到达不了（就是支配点的概念）。

n\leq 2\cdot10^5$ ， $m\leq 3\cdot 10^5

前肢假想

根据题目，我们以此来建一个树，称之为“支配树”

满足“支配树”要满足这些性质：

1.这是一个树（而不是图），根节点就是起点；

2.对于任意点 u ，从根到它的简单路径上的所有点都是它的支配点；

3.对于任意点 u ，它支配它的子树上所有的子孙节点。

如果能这样造出来，问题就解决了。

前肢引入

Lengauer-Tarjan 算法

哪里都有 Tarjan 老爷子。。。 Tarjan orz ！

Lengauer-Tarjan 算法主要分了三个步骤：

1.从起点开始造 dfs 树并求出所有点的 dfn ；

2.求出所有点的半支配点；（暂设数组 semi(i) ）

3.求出所有点的支配点。（暂设数组 idom(i) ）

其中半支配点是一个新概念，也是间接求支配点的精髓。

对于任意点 u 的半支配点表示所有点中有 dfn 最小的点 v ，能使 v 满足有一条路径能够到达 u 且路径上的所有点（ u 和 v 都不算）的 dfn 都大于 dfn(u) 。

猪蹄内容

就只讲讲一般有向图吧，因为这个解决了其他的就都解决了（如树， DAG ）。

丝绸之路的诞生之半支配点

设目前我们在研究点 u ，那么再设点 v 指所有直接连向 u 的点。

分类讨论（王道！）

1.dfn(v)=dfn(u)

直接无解。。跳过。

2.dfn(v)<dfn(u)

如果要从这条路径上走的话，刚开始就结束了（根据定义来），所以把 v 和可能存在的 semi(u) 择优更新就好了。

3.dfn(v)>dfn(u)

那么就在 dfs 树上从 v 找一个祖先 w 且 dfn(w)>dfn(u) ，然后就把可能存在的 semi(w) 和可能存在的 semi(u) 择优更新。

因为既然有了 semi(w) ，这一段路径上所有 dfn 都大于 dfn(u) （定义来的）， w 又是从 semi(u) 到 u 的路径上搜到的，所以 w 之后的点也满足。

（不是很懂？？正常，我也有点云里雾里的（就算明白了，一会也就忘了），但关键好背！！）

至此，半支配点完结！

丝绸之路的诞生之支配点

考虑在半支配点的肩膀上求出支配点。

设目前我们在研究点 u 。

然后记一个点集 \large\xi 表示在 dfs 树上从 semi(u) 到 u 的路径的点集，（但不包括 semi(u) ）其中点 \alpha 是 \large\xi 中 dfn(semi) 最小的点。

那么，分类讨论（王道！）

（肯定是判断 semi 相等而不是比较 dfn 大小了呀）

1.semi(\alpha)=semi(u)

则 idom(u)=semi(u) 。

因为 \alpha 已经是 semi(u) 到 u 路径中所有点的下限（ dfn(semi) ）了，如若当前情况就是 \large\xi 成了个封闭的点集， semi(u) 是唯一直接相连的点，自然就有了 idom(u)=semi(u) 。

2.semi(\alpha)\neq semi(u)

则 idom(u)=idom(\alpha) 。

感性理解：

倘若有这么一个“中间点” \beta 。

我们假设没有了 idom(\alpha) ， u 还可以能够到达。那么说明 idom(\alpha) 祖先会有一个点有一条非 dfs 树边连向了 idom(\alpha) 和 u 中间的一个点 \beta 。

其中， \alpha 必是 \beta 的祖先，否则没有了 idom(\alpha) 也能到达 \alpha ，显然与定义不符。

如若如此， \beta 便一定在 \large\xi 中了。

看得出来， semi 的要求比 idom 高一些，从满足条件的难度上，所以 dfn(idom(\alpha))\leq dfn(semi(\alpha)) 显然。（记住，这是感性。。）

但 idom(\alpha) 的祖先有一条非 dfs 树边连向了 \beta ，所以无论如何 dfn(semi(\beta))<dfn(idom(\alpha)) 。

结合上面的两段内容，发现会与 \large\xi 关于 \alpha 的定义不符了。所以没有了 idom(\alpha) ， u 一定不能够到达。

至此，支配点完结！

从丝绸之路到实际实现

1.半支配点

如果还有点印象的话，应该能知道求解过程都是 dfn 从大到小的逆推，所以可以倒序 dfn 处理。

对于第二个情况（第一个就。。）直接干，而第三种情况，肯定是不会暴力枚举的。

于是考虑一个带权并查集（说的好像要怎么样，但代码就是好背），每次处理完一个点，就往它在 dfs 树上的点合并，按照支配点中 \large\xi 的要求维护对应的东西。

2.支配点

很多辅助东西都与半支配点一并整好了，只需要把已经求的 semi 与对应的点连边，构造半支配树，就能同时求解支配点。

由于可能存在搜索的时候 idom 并未找到，可以先记录下来，最后顺序 dfn 再额外处理。

但还有要注意的是（出自于 hezlik 佬）。

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

时间复杂度 O(n\log_{2}{n}) ，优雅的诠释了Lengauer-Tarjan 算法的优越性。

（没办法， Tarjan 老爷子就这么厉害。。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10,M=3e5+10;
int n,m,ans[N],tot;
int fst[N][3],nxt[M+M+N],to[M+M+N];
int dfn[N],ord[N],cnt,fth[N];
int idom[N],semi[N],uni[N],mn[N];
inline ll read()
{
    ll s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline void add(int u,int v,int id)
{
    nxt[++tot]=fst[u][id];
    to[tot]=v,fst[u][id]=tot;
}
inline void Tarjan(int u)
{
    ord[dfn[u]=++cnt]=u;
    for(int i=fst[u][0];i;i=nxt[i])
    {
        int v=to[i];
        if(!dfn[v])
        {
            fth[v]=u;
            Tarjan(v);
        }
    }
}
inline int uni_query(int u)
{
    if(u==uni[u])return u;
    int tmp=uni_query(uni[u]);
    if(dfn[semi[mn[u]]]>dfn[semi[mn[uni[u]]]])mn[u]=mn[uni[u]];
    return uni[u]=tmp;
}
inline void Lengauer_Tarjan(int s)
{
    Tarjan(s);
    for(int i=1;i<=n;++i)semi[i]=uni[i]=mn[i]=i;
    for(int id=cnt;id>=2;--id)
    {
        int u=ord[id];
        for(int i=fst[u][1];i;i=nxt[i])
        {
            int v=to[i];
            if(!dfn[v])continue;
            uni_query(v);
            if(dfn[semi[u]]>dfn[semi[mn[v]]])semi[u]=semi[mn[v]];
        }
        uni[u]=fth[u];
        add(semi[u],u,2);
        u=fth[u];
        for(int i=fst[u][2];i;i=nxt[i])
        {
            int v=to[i];
            uni_query(v);
            idom[v]=(u==semi[mn[v]]?u:mn[v]);
        }
        fst[u][2]=0;
    }
    for(int i=2;i<=cnt;++i)
    {
        int u=ord[i];
        if(idom[u]^semi[u])
        idom[u]=idom[idom[u]];
    }
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;++i)
    {
        int x=read(),y=read();
        add(x,y,0),add(y,x,1);
    }
    Lengauer_Tarjan(1);
    for(int i=cnt;i>=2;--i)ans[idom[ord[i]]]+=(++ans[ord[i]]);
    ++ans[1];
    for(int i=1;i<=n;++i)printf("%d ",ans[i]);
    return 0;
}

只求能帮助到几个人罢。。