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

凌乱 · 2019-08-02 10:18:38 · 题解

蒟蒻的题解

题目分析： 首先肯定是个模板题啦，一个有向图，给你一个起点，求每个点的支配的点的个数

一些定义：

支配点： 从u到v的所有路径如果都经过一个点p，那么我们称这个点p为v的支配点，如果把p切掉，那么u将无法到达v，显然一个点的支配点可以有很多个(比如：) 对于这个图从0出发，7的支配点有3和6

半支配点： 存在从一个点u到v的路径中(不包括u，v)，所有的点pi的dfn都大于v的dfn(下面两个点的比较大小都指的是他们的dfn)(我们在做题前是要扣出一个dfs树的)，当然如果u是v在dfs树上的父节点，那么u也是v的半支配点

一些准备:

为什么要求支配点： 因为我们是做不到直接求支配点的，支配点一定是半支配点，所以我们要找到所有点的半支配点，然后去求支配点，所有半支配点都有机会成为支配点，我们用semi[v]数组来表示v点的所有半支配点的最小的那个

原理： 具体原理其实很多大佬已经讲得很详细了，欢迎看完了他们的讲解再来看我的题解，然后我帮你水过这个题(因为他们讲的太过详细(所以就不一定能够完全看的懂))(最好还是先去他们那里水个几个小时) 因为这里的小蒟蒻并不会讲太多的原理基本没有

基本思路：

树如果原图是一个树那么他就是我们要的支配树，dfs一遍求出每个点的所在子树的大小就是支配的点数啦
DAG 对于一个DAG，我们先拓扑，对于每一个点u，他的直接前驱f1，f2.....fn 这些f的lca(设他为fafa)，那么fafa就是u在支配树上的父节点，那么我们支配树就建完了，那么我们就得到了一棵树，然后看上面
一般图 对于一般的图，我们需要先扣出一个dfs树，然后求出所有的点u(不包括起点)的semi[u]，然后再在dfs树上连接（semi[u],u）（这样所有的点的支配关系是不变的）然后我们就把这个dfs树变成了一个DAG，然后看上面，然后大家可以先做一下这道题p2597和这个题（这两个都是DAG，可以练练手）
我觉得有必要给出样例的图

上代码：

# include <iostream>
# include <cstdio>
# include <cstring>
# include <queue>
# define sz 20
# define FOR(i,st,ed) for(int i=st;i<=ed;++i)
# define _FOR(tu,u) for(int v,i=tu.hd[u];i;i=tu.e[i].nt)
# define _(tu) v=tu.e[i].to;
using namespace std;
int re(){
    int s=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){s=(s<<1)+(s<<3)+ch-'0';ch=getchar();}
    return s*f;
}//快读就不解释了

const int N=2e5+7;
struct MAP{
    struct edge{
        int to,nt;
    }e[N<<1];int cnt,hd[N];
    void link(int x,int y){e[++cnt]=(edge){y,hd[x]};hd[x]=cnt;}
}xx,a,ra,t,rt,z;//排除xx，依次表示原图，原图的反图，dfs树
//dfs树的反图，和最后的支配树
int n,m;

int dfn[N],dji,id[N],ff[N];//ff表示dfs树上的父节点
void dfs(int u){
    id[dfn[u]=++dji]=u;
    _FOR(a,u){
        _(a);
        if(!dfn[v]) dfs(v),ff[v]=u,t.link(u,v); 
    }
}//扣出一个dfs树

int anc[N],semi[N],mn[N];//这个mn[v],表示v点的dfs树上的祖先
//的semi最小的那个祖先，所以semi[mn[x]]=semi[x];
void init(){
    FOR(i,1,n) anc[i]=semi[i]=mn[i]=i;
}
int find(int u){
    if(u!=anc[u]){
        int t=anc[u];anc[u]=find(anc[u]);
        if(dfn[semi[mn[u]]]>dfn[semi[mn[t]]]) mn[u]=mn[t];
    }
    return anc[u];
}//以上是带权并查集(路径压缩)
void len_tarjan(){
    init();
    for(int j=n;j>=2;--j){
        int u=id[j],res=j;
        if(!u) continue;
        _FOR(ra,u){
            _(ra);
            if(!dfn[v]) continue;
            if(dfn[v]<dfn[u]) res=min(res,dfn[v]);
            else find(v),res=min(res,dfn[semi[mn[v]]]);
        }
        semi[u]=id[res];anc[u]=ff[u];t.link(semi[u],u); 
    }
}//我们的tarjan大佬的算法

int ru[N],dep[N],fa[N][25];
int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    int del=dep[x]-dep[y];
    FOR(i,0,sz)
        if((1<<i)&del) x=fa[x][i];
    if(x==y) return x;
    for(int i=sz;i>=0;--i)
        if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}/lca
void work(int u){
    int t=rt.e[rt.hd[u]].to;
    _FOR(rt,u){
        _(rt);t=lca(t,v);
    }
    dep[u]=dep[t]+1;
    fa[u][0]=t;
    z.link(t,u);
    FOR(i,1,sz)
        fa[u][i]=fa[fa[u][i-1]][i-1]; 
}//建立支配树
void tpsort(){
    FOR(j,1,n)
        _FOR(t,j){
            _(t);
            ru[v]++;rt.link(v,j); 
        }   
    FOR(i,1,n) if(!ru[i]) t.link(0,i),rt.link(i,0);
    queue <int> q;q.push(0);
    while(q.size()){
        int u=q.front();q.pop();
        _FOR(t,u){
            _(t);
            if((--ru[v])<=0) q.push(v),work(v);
        }
    } 
}

int siz[N];
void adfs(int u){
    siz[u]=1;
    _FOR(z,u){
        _(z);adfs(v);siz[u]+=siz[v];
    }
}//最后adfs用来搜答案
int main(){
    n=re();m=re();int x,y;
    FOR(i,1,m){
        x=re();y=re();
        a.link(x,y);ra.link(y,x);  
    }
    dfs(1);
    len_tarjan();
    tpsort();
    adfs(0);
    FOR(i,1,n) cout<<siz[i]<<' ';
    return 0;
}//好的 我们成功的水了一道黑题!