支配树学习笔记

部分题解内容转自博客:
https://blog.csdn.net/litble/article/details/83019578
https://www.luogu.org/blog/28007/post-2597-post
https://xzyxzy.blog.luogu.org/solution-p5180

what is 支配点

很久很久以前,有一张有向图,有向图有一个起点S,有一个叫小X的强盗,占据一个点拦路打劫。当小X占据了x 点后,若从S出发就到不了y点了,那么x就是y的支配点。

而支配树,就是满足树上一个点x的所有祖先都是它的支配点的树。

How to build 支配树

以下我们假定从S出发可以到达图上所有点。

树形图

显然,树形图自己就是自己的支配树。

DAG

DAG的话,我们按照拓扑序从小到大进行,假设处理到点x ,则查一遍所有可达点x的点y,所有点y一定被加入了支配树中,那么它们在支配树上的LCA就是x在支配树上的父亲,倍增就可以做到$O(nlogn)$,读起来非常绕口,所以接下来用图来解释一下。
例题洛谷P2597 灾难
先来看样例:
这里为什么要反向存图呢?因为高级捕食者要捕食低级捕食者(生产者)。如果所有指向他的点(低级捕食者)都没了。他也肯定会死。
然后接着下看。
如果我们只用赤果果的topsort+递推。节点4(下同)就会卡掉你。
我们怎么改进呢?
我们可以将节点4复制一份影分身! 再利用边的有向性。建一颗树。
如图
这样的话我们就将问题转换为求以 节点x 为根的子树的节点的个数,再去一个重。
可是这样的话,最难的问题就变成了去重。
我们先等一等。再想一想4和4* 的性质只有节点1死了。4才会死尽。
而节点1是什么呢?是4和4* 的最近公共祖先。

就像这个样子

我们在topsort建树中,扫描到了4。 根据我们之前找的道理。我们需要找他们的最近公共祖先并且链上去。
一个很简单的性质。对于样例,我们只需要找出2,3(就是在我们第2个图没有缩点之前中4和4* 的父亲,图2是我们为了理解的一个过程的树),就是所有指向他的节点在我们以及建好了的树中(无影分身版)的lca。

代码如下:
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
const int inf=0x3f3f3f3f;
vector<int>g[maxn],fg[maxn],tr[maxn];
int du[maxn],p[maxn],dep[maxn],ans[maxn],fa[maxn][20];
int tot=0;
int n;
void topsort(){
    for(int i=1;i<=n;i++){
        if(!du[i])
            g[0].push_back(i),fg[i].push_back(0),du[i]++;
    }
    stack<int>q;
    q.push(0);
    while(!q.empty()){
        int x=q.top();
        q.pop();
        p[tot++]=x;
        for(int v:g[x]){
            du[v]--;
            if(du[v]==0)
                q.push(v);
        }
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=15;i>=0;i--){
        if(dep[fa[x][i]]>=dep[y])
            x=fa[x][i];
    }
    if(x==y)return x;
    for(int i=15;i>=0;i--){
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    }
    return fa[x][0];
}
void dfs(int x){
    ans[x]=1;
    for(int v:tr[x]){
        dfs(v);
        ans[x]+=ans[v];
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin>>n;
    int x;
    for(int i=1;i<=n;i++){
        cin>>x;
        while(x){
            g[x].push_back(i);
            fg[i].push_back(x);
            du[i]++;
            cin>>x;
        }
    }
    topsort();
    for(int i=1;i<=n;i++){
        int x=p[i],y=fg[x][0];
        for(int v:fg[x])
            y=lca(y,v);
        tr[y].push_back(x);
        dep[x]=dep[y]+1;
        fa[x][0]=y;
        for(int j=1;j<=15;j++)
            fa[x][j]=fa[fa[x][j-1]][j-1];
    }
    dfs(0);
    for(int i=1;i<=n;i++)cout<<ans[i]-1<<endl;
    return 0;
}

普通有向图

首先把原图dfs一遍,求出df序

半支配点
通俗一点:从semi[x]到xx的路径,掐头去尾,都走的dfn大于x的点

画个图大概就是如下,dfn[]={0,1,2,3,4,5,7,6},2->6->5掐头去尾的dfn都大于dfn[5]

性感地理解就是:semi[x]到x的路径相当于是在dfs树外有一条路,且semi[x]是离根最近的那个点,从semi[x]都走不到x了,那其他的点更走不到了

由此可以得出一种做法,求出semisemi后转DAG的做法,复杂度O(nlogn)

代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+100;
const int inf=0x3f3f3f3f;
int n,m;
vector<int>g[maxn],fg[maxn],b[maxn],e[maxn],tr[maxn];
int dfn[maxn],id[maxn],anc[maxn],top[maxn],dep[maxn],ans[maxn],
    semi[maxn],mn[maxn],in[maxn],fa[maxn][20],faa[maxn];
int tot,cnt=0,start;
void init() {
    tot=cnt=0;
    start=n;//起点
    for(int i=0; i<=n; i++) {
        g[i].clear();
        fg[i].clear();
        b[i].clear();
        e[i].clear();
        tr[i].clear();
        dfn[i]=id[i]=ans[i]=in[i]=anc[i]=dep[i]=0;
        faa[i]=mn[i]=semi[i]=i;
        for(int j=0; j<=18; j++) {
            fa[i][j]=0;
        }
    }
}
void dfs(int x,int f) {
    dfn[x]=++tot;
    id[tot]=x;
    anc[x]=f;//anc[x]表示x在dfs树上的父亲
    b[f].push_back(x);//dfs树
    for(int v:g[x]) {
        if(!dfn[v])
            dfs(v,x);
    }
}
void topsort() {
    stack<int>q;
    for(int i=1; i<=n; i++) {
        if(!in[i])
            q.push(i);
    }
    while(!q.empty()) {
        int x=q.top();
        q.pop();
        top[++cnt]=x;
        for(int v:b[x]) {
            in[v]--;
            if(!in[v])
                q.push(v);
        }
    }
}
//其中find(R)find(R)表示路径压缩的带权并查集,维护RR到其已经被
//搜过的祖先的 dfndfn的最小值mn[R]mn[R],用semi[mn[R]]semi[mn[R]]
//去更新semi[x]semi[x] 然后例题就得到了一种O(nlog)O(nlog)的做法
int find(int x) {
    if(x==faa[x])
        return x;
    int tt=faa[x];
    faa[x]=find(faa[x]);
    if(dfn[semi[mn[tt]]]<dfn[semi[mn[x]]])
        mn[x]=mn[tt];
    return faa[x];
}
int lca(int x,int y) {
    if(dep[x]<dep[y])
        swap(x,y);
    for(int i=18; i>=0; i--) {
        if(dep[fa[x][i]]>=dep[y])
            x=fa[x][i];
    }
    if(x==y)
        return x;
    for(int i=18; i>=0; i--) {
        if(fa[x][i]!=fa[y][i]) {
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    return fa[x][0];
}
void dfscal(int x,int data) {
    ans[x]=x+data;
    for(int v:tr[x]) {
        dfscal(v,data+x);
    }
}
void solve() {
    dfs(start,0);
    //按照dfndfn序从大到小做,对于xx,枚举RR存在R->xR−>x这条边
    for(int i=n; i>=2; i--) {
        int x=id[i],res=n;
        if(!x)
            continue;
        for(int v:fg[x]) {//反图
            if(!dfn[v])//有可能root不能走到y
                continue;
            if(dfn[v]<dfn[x])
                res=min(res,dfn[v]);
            else
                find(v),res=min(res,dfn[semi[mn[v]]]);
        }//anc[x]表示x在dfs树上的父亲
        semi[x]=id[res];
        faa[x]=anc[x];
        b[semi[x]].push_back(x);
    }
    //b为DAG图,下面开始建DAG图的反边
    for(int i=1; i<=n; i++) {
        for(int v:b[i]) {
            in[v]++;
            e[v].push_back(i);
        }
    }
    topsort();
    //x连接到它所有父节点的lca上
    for(int i=1; i<=cnt; i++) {
        int x=top[i],y=0;
        if(e[x].size())
            y=e[x][0];
        for(int v:e[x])
            y=lca(y,v);
        fa[x][0]=y;
        dep[x]=dep[y]+1;
        tr[y].push_back(x);
        for(int j=1; j<=18; j++)
            fa[x][j]=fa[fa[x][j-1]][j-1];
    }
    dfscal(start,0);
}
int main() {
    ios::sync_with_stdio(false);
    while(cin>>n>>m) {
        init();
        for(int i=1; i<=m; i++) {
            int x,y;
            cin>>x>>y;
            //swap(x,y);
            g[x].push_back(y);
            fg[y].push_back(x);
        }
        solve();
        for(int i=1; i<=n; i++) {
            cout<<ans[i]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注