学习笔记 支配树

tcswuzb · 2019-01-10 12:24:00 · 题解

注明参考出处

膜拜巨佬之余

来一个Tarjan老爷子的Lengauer-Tarjan算法吧

最优是O(nα(n)) 但是会被卡成O(nlogn)

(这里默认nm数量级同阶)

1.定义

对于一棵可以存在环的有向图

给定一个起点r 对于一个终点x 如果r到达x的所有路径都会经过一个点y

那么我们就称之为y支配x

我们令支配x的点集为S=p_1,p_2,p_3,......,p_k

那么从起点r到达x的任意一条路径排列为r......p_1......p_2......p_k...x

支配树可以对于每一个点x(x!=r)求出p_k 也就是点集S当中距离x最近的支配点

这个点我们称之为idom[x]

如果每一个点连出指向idom[x] 那么就构成了一颗内向树 我们称之为支配树

2.算法

1.首先我们需要一颗DFS树

也就是对这个算法进行dfs遍历 求出其dfs序

2.半必经点

从y出发到x 存在这样一条路径 路径上的点(不包括x以及y)的dfn均大于dfn[x] 我们称y是x的半必经点

若dfn[y]<dfn[x] 且dfn[y]比当前找到的sdom[x]的dfn小 那么就用sdom[x]=y

若dfn[y]>dfn[x] 找打树上y的一个祖先z 并且dfn[z]>dfn[x] 比较dfn[sdom[z]]同dfn[sdom[x]] 决定是否用前者更新后者

从半支配点到支配点

对于x 我们要的是idom[x]

寻找方法如下

我们令P是从sdom[x]到x的树上路径点集(不包括sdom[x]) 而且z是P中dfn[sdom[z]]最小的点

如果sdom[z]=sdom[x] 那么idom[x]=sdom[x] 否则就是idom[x]=idom[z]

算法流程

我们用带权并查集来实现

首先按照dfs序从大到小处理 每一次处理完毕一个点之后 将这个点同其在dfs树上的父亲在并查集连边

而并查集的权 就是并查集这个点到根节点的路径上的所有点 最小的dfn[sdom[x]]对应的x

找sdom[]直接找即可 找idom可以使用sdom[x]处理

CODE:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<list>
#include<set>
#include<deque>
#include<vector>
#include<ctime>
#define ll long long
#define inf 0x7fffffff
#define N 500008
#define IL inline
#define M 1008611
#define D double
#define ull unsigned long long
#define R register
using namespace std;
template<typename T>void read(T &a)
{
    T x=0,f=1;char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=0;ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+ch-'0';ch=getchar();
    }
    a=f?x:-x;
}
/*-------------OI使我快乐-------------*/
int n,m,tot,cnt;
int head[M<<1],pre[N<<1],to[N<<2],nex[N<<2],lat[M],cdy[M];
int bel[M],val[M],sdom[M],idom[M],ans[M];
int dfn[M],id[M],fa[M];
IL void add(int *h,int x,int y)
{to[++tot]=y;nex[tot]=h[x];h[x]=tot;}
IL void dfs(int now)
{
    dfn[now]=++cnt;id[cnt]=now;
    for(R int i=head[now];i;i=nex[i])
    {
        int v=to[i];
//      printf("%d --> %d\n",now,v);
        if(dfn[v]) continue;
        dfs(v);fa[v]=now;
    }
} 
IL int find(int x)
{
    if(x==bel[x]) return x;
    int root=find(bel[x]);
    if(dfn[sdom[val[bel[x]]]]<dfn[sdom[val[x]]])
    val[x]=val[bel[x]];
    return bel[x]=root;
}
IL void Tarjan()
{
//  for(R int i=1;i<=n;++i) printf("dfn[%d] %d\n",i,dfn[i]);
    for(R int i=cnt;i>=2;--i)
    {
        int now=id[i];
        //我们按照dfs序 从大到小处理 节点 
        for(R int j=pre[now];j;j=nex[j])
        {//这里用链式前向星 存入度节点 
            int v=to[j];
            if(!dfn[v]) continue;
            find(v);
            //dfn[y]<dfn[x]的话  
            //我们还未处理到 sdom[y]=val[y]=y 
            //此时y的并查集树中只有TA自己 更新是合法的 

            //dfn[y]>dfn[x]的话
            //就按照套路比较 
            if(dfn[sdom[val[v]]]<dfn[sdom[now]])
            sdom[now]=sdom[val[v]];
        }
        add(lat,sdom[now],now);
        bel[now]=fa[now];
        //同其在dfs树上的父亲连边 
        now=fa[now];
        //现在父亲到TA这棵子树已经处理完了
        //所以此时我们可以对
        //以父亲为sdom[x]的x分别求一次sdom  然后清空
        //对于每一个点进行更新 
        for(R int j=lat[now];j;j=nex[j])
        {
            int v=to[j];
            find(v);
            if(sdom[val[v]]==now) idom[v]=now;
            //如果sdom[z]==sdom[x] 那么idom[x]=sdom[x]
            //此时sdom[x]=now 
            else idom[v]=val[v];
            //否则就是idom[x]=idom[z] 
            //但是实际实现我们可以写成idom[x]=z
            //然后在接下来处理 
        }
    }
    for(R int i=2,now;i<=cnt;++i)
    {
        now=id[i];
        if(idom[now]!=sdom[now]) idom[now]=idom[idom[now]];
        //这是残余节点的填坑大作战 
    }
}
IL void dfs_ans(int now)
{
    ans[now]=1;
    for(R int i=cdy[now];i;i=nex[i])
    {
        int v=to[i];
        dfs_ans(v);
        ans[now]+=ans[v];
    }
}
int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    read(n);read(m);
    for(R int i=1,x,y;i<=m;++i)
    {
        read(x);read(y);
        add(head,x,y);add(pre,y,x);
    }
    for(R int i=1;i<=n;++i)
    sdom[i]=bel[i]=val[i]=i;
    dfs(1);
    Tarjan();
//  puts("How old are you ? ");
//  for(int i=1;i<=n;++i)
//    {
//      printf("支配点[%d]   %d\n",i,idom[i]);
//    } 
    tot=0;
    for(R int i=2;i<=n;++i) if(idom[i]) add(cdy,idom[i],i);
    dfs_ans(1);
    for(R int i=1;i<=n;++i) printf("%d%c",ans[i],(i==n ? '\n':' '));
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

HEOI 2019 RP++