支配树

这玩意。。真的不是很懂

给定一张有向图和源点 $S$ ，若去掉点 $i$ 则点 $j$ 不可从 $S$ 到达则称 $i$ 支配 $j$ 。求每个点支配的点的个数。

（首先本来S就不可达的点与本问题没有关系，统统去掉。下面默认只有 $S$ 一个点入度为 $0$ 。）

首先，支配关系显然是具有传递性质的。于是可以想到所有的支配关系构成了一棵树。也就是支配树。点 $y$ 能支配点 $x$ 当且仅当 $y$ 是 $x$ 的祖先。

首先简化版的问题是图没有环，是个DAG。

首先 $S$ 一定是支配树的根。而去掉 $S$ 之后入度为 $0$ 的点只被 $S$ 支配，应是 $S$ 的儿子。这启发我们拓扑排序构建支配树。

对于一个点 $x$ ，它在支配树上的父亲应是所有存在 $(y,x)$ 边的 $y$ 在支配树上的 $lca$ （很好理解，需要让所有的 $y$ 都被支配）。

需要边拓扑边维护倍增数组。

于是上代码。。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+50;
int n,ver[N],nxt[N],head[N],tot,du[N],st[N],d[N],tp,f[N][20],l[N],sz[N],dd[N];bool flag[N];
int read(){
    int x=0,c;
    while(!isdigit(c=getchar()));
    while(isdigit(c))x=x*10+(c^48),c=getchar();
    return x;
}
void add(int x,int y){ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;du[y]++;}
int lca(int x,int y){
    if(d[x]<d[y])swap(x,y);
    for(int i=18;~i;i--)if(d[f[x][i]]>=d[y])x=f[x][i];
    if(x==y)return x;
    for(int i=18;~i;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    return f[x][0];
}
int main(){
    n=read();
    for(int i=1,x;i<=n;i++)while((x=read()))add(x,i);
    for(int i=1;i<=n;i++)if(!du[i])add(n+1,i);
    st[tp=1]=n+1;
    while(tp){
        int x=st[tp--];d[x]=d[l[x]]+1;f[x][0]=l[x];dd[l[x]]++;
        for(int i=0;i<18;i++)f[x][i+1]=f[f[x][i]][i];
        for(int i=head[x],y;i;i=nxt[i]){
            if(!--du[y=ver[i]])st[++tp]=y;
            l[y]=l[y]?lca(l[y],x):x;
        }
    }
    for(int i=1;i<=n;i++)if(!dd[i])st[++tp]=i;
    while(tp){
        int x=st[tp--],y=f[x][0];sz[x]++;
        sz[y]+=sz[x];if(!--dd[y])st[++tp]=y;
    }
    for(int i=1;i<=n;i++)printf("%d\n",sz[i]-1);
    return 0;
}

然后是神仙的带环。。真的不懂。。EI说根本就没考过支配树。。看来还是太神仙了。。

tarjan和另一个神仙发明的算法qwq

这个算法关键是要构造出一张新图，这张图上没有环，而且支配关系和原图一样。

我们先给这张图从 $S$ dfs一遍，求出一个dfs序和一棵dfs树。

下面就是感性理解了呜呜呜

我们发现 $x$ 在支配树上的父亲一定是 $x$ dfs树上的祖先。。

设这个点是 $y$ ，它怎么到 $x$ 呢？一种是走dfs树上的路径，好，那我们把dfs树上的边都塞到新图里。。
还有一种是走dfs树外的边。这种路径长啥样？
$y->v_1->v_2->\dots ->v_m->x$ ，其中 $v_1\dots v_m$ 的dfs序都大于x的

为啥？不知道。。画图可能可以理解。。困难。。

这样的话，我们可以求出dfs序最小的 $y$ 使得存在这样的路径（经过的点dfs序都大于x的），在新图中连上 $(y,x)$ 。

这样的点 $y$ 称为 $x$ 的半支配点。然后我们现在只要可以求出半支配点，就撒花了。

我们考虑按dfs序倒序枚举每个点 $x$ ，遍历反图中的边（即所有的 $(y,x)$ ）
若 $dfn[y]<dfn[x]$ 拿 $y$ 更新 $x$ 。否则 $y$ 可以作为那种合法路径中的点。还有一个结论是那种路径的 $v_1\dots v_m$ 一定是dfs树上的链。。。~~wdnmd~~所以我们拿带权并查集维护一下当前的这个点往上跳dfs序还大于 $x$ 的半支配点dfs序最小的点是啥。。

放代码。。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+50;
int n,m,dfn[N],idfn[N],cnt,ff[N],fa[N],g[N],st[N],tp,l[N],dep[N],f[N][20],d[N],sz[N];
struct node{
    int ver[N*2],nxt[N*2],head[N],d[N],tot;
    void add(int x,int y){ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;d[y]++;}
}A,B,C,D;
int find(int x){
    if(fa[x]==x)return x;
    int f=fa[x];fa[x]=find(fa[x]);
    g[x]=min(g[x],g[f]);return fa[x];
}
int read(){
    int x=0,c;
    while(!isdigit(c=getchar()));
    while(isdigit(c))x=x*10+(c^48),c=getchar();
    return x;
}
void dfs(int x){
    idfn[dfn[x]=++cnt]=x;
    for(int i=A.head[x],y;i;i=A.nxt[i])
        if(!dfn[y=A.ver[i]])C.add(x,y),ff[y]=x,dfs(y);
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=18;~i;i--)if(dep[f[x][i]]>=dep[y])x=f[x][i];
    if(x==y)return x;
    for(int i=18;~i;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    return f[x][0];
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<=m;i++){
        x=read(),y=read();
        A.add(x,y),B.add(y,x);
    }
    dfs(1);
    for(int i=1;i<=n;i++)fa[i]=i,g[i]=1e9;
    for(int _=cnt;_>1;_--){
        int x=idfn[_],mn=1e9;
        for(int i=B.head[x],y;i;i=B.nxt[i])
            if(dfn[y=B.ver[i]]<dfn[x])mn=min(mn,dfn[y]);
            else find(y),mn=min(mn,g[y]);
        C.add(idfn[mn],x);fa[x]=ff[x];g[x]=mn;
    }
    st[tp=1]=1;
    while(tp){
        int x=st[tp--];dep[x]=dep[l[x]]+1;f[x][0]=l[x];d[l[x]]++;
        for(int i=0;i<18;i++)f[x][i+1]=f[f[x][i]][i];
        for(int i=C.head[x],y;i;i=C.nxt[i]){
            if(!--C.d[y=C.ver[i]])st[++tp]=y;
            l[y]=l[y]?lca(l[y],x):x;
        }
    }
    for(int i=1;i<=cnt;i++)if(!d[idfn[i]])st[++tp]=idfn[i];
    while(tp){
        int x=st[tp--],y=l[x];sz[x]++;
        if(!--d[y])st[++tp]=y;
        sz[y]+=sz[x];
    }
    for(int i=1;i<=n;i++)printf("%d ",sz[i]);
    return 0;
}

真恶心了。。有生之年再来补吧。。

这篇博客有详细证明

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=2e5+50;
int n,m,dfn[N],idfn[N],fa[N],cnt,sdom[N],idom[N],f[N],g[N],sz[N],p[N];
vector<int>v[N],vv[N],hav[N];
void dfs(int x){
    idfn[dfn[x]=++cnt]=x;
    for(int i=0,y;i<v[x].size();i++)
        if(!dfn[y=v[x][i]])fa[y]=x,dfs(y);
}
int find(int x){
    if(f[x]==x)return x;
    int ff=f[x];f[x]=find(ff);
    dfn[sdom[g[ff]]]<dfn[sdom[g[x]]]?g[x]=g[ff]:0;
    return f[x];
}
int main(){//以下比较均为dfs序比较（用dfs序重编号了）
    //只有两个重要结论：sdom(w)=min({u|(u,w)\in E}并{sdom(u)|u>w,存在(v,w)\in E,u是v祖先})（这个还是很好证的，感性也好理解）
    //令u为所有在sdom(w)到w链上的点（除了sdom(w)）中sdom最小的点，则(idom(w)=sdom(u)<sdom(w)?idom(u):sdom(w))（这个证起来就很神仙）
    scanf("%d%d",&n,&m);
    for(int i=1,x,y;i<=m;i++)
        scanf("%d%d",&x,&y),
        v[x].pb(y),vv[y].pb(x);
    dfs(1);for(int i=1;i<=n;i++)g[i]=sdom[i]=f[i]=i;
    for(int i=n;i>1;i--){//计算sdom按dfs序倒序好计算
        int x=idfn[i],mn=n;
        for(int j=0,y;j<vv[x].size();j++)
            find(y=vv[x][j]),mn=min(mn,dfn[sdom[g[y]]]);
        hav[sdom[x]=idfn[mn]].pb(x);f[x]=fa[x];x=fa[x];
        for(int j=0,y;j<hav[x].size();j++)//访问到x说明x的子树都访问完了，而fa[x]没有访问过，这时可以正确地更新所有sdom是fa[x]的点的u。
            find(y=hav[x][j]),p[y]=g[y];
        hav[x].clear();
    }
    for(int i=2,x;i<=n;i++)x=idfn[i],idom[x]=sdom[p[x]]^sdom[x]?idom[p[x]]:sdom[x];
    for(int i=n,x;i;i--)sz[x=idfn[i]]++,sz[idom[x]]+=sz[x];
    for(int i=1;i<=n;i++)printf("%d ",sz[i]);
    return 0;
}

Prutekoi's blog

常系数齐次线性递推