题解 P5180 【【模板】支配树】
说实话题解全在注释里了
事实上我是三篇博客一起看才理解的
这里推荐两篇不错的博客
证明非常严谨，也很好懂
神仙“性感”理解法
#include<iostream>
#include<cstdio>
#include<cstring>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Ford(i,a,b) for(int i=a;i>=b;i--)
const int N=2e5+100,M=3e5+1000;
void read(int &x)
{
int t=0,opt=1;
char c=getchar();
while (c<'0'||c>'9') (c=='-'?opt=-1:0),c=getchar();
while ('0'<=c&&c<='9')
{
t=t*10+c-'0';
c=getchar();
}
x=t*opt;return ;
}
int n,m,x,y,idom[N],sdom[N];
int nex[N],pre[N],sdom_nex[N],idom_nex[N];
int Next[2*M+N+N],d[2*M+N+N],tol=0;
void Link(int *nex,int x,int y)
{
Next[tol]=nex[x];
nex[x]=tol;
d[tol]=y;
tol++;
}
int dfn[N],cnt,pos[N],pa[N];
void dfs(int now)
{
dfn[now]=++cnt;pos[cnt]=now;
for (int p=nex[now];p!=-1;p=Next[p]) if (!dfn[d[p]])
pa[d[p]]=now,dfs(d[p]);
}
namespace Set
{
int pa[N],min[N];
int Find(int x)
{
if (x==pa[x]) return x;
int ans=Find(pa[x]);
if (dfn[sdom[min[pa[x]]]]<dfn[sdom[min[x]]]) min[x]=min[pa[x]];
return pa[x]=ans;
}
} ;
void Tarjan()
{
Ford(i,n,2) //将搜索树上s到他的路径理解为s到他的第一条路径
{
int now=pos[i];
//把sdom视为树外边（因为树上路径一定是第一条路径，sdom不可能从小于当前根的子树过来）
//枚举 d[p]->now ，从他们到 他们和now的LCA 的路上取最小的sdom[]
//因为经过d[p]到now的合法且可能更新sdom[now]的路径
//1）起点一定是now的祖先 （sdom[now]<=fa[now],且引理：dfn小于now的点到now一定经过其和now的祖先）
// 证引理：想象一下有一棵建了一半的搜索树，一个点x，他要到一个还没有遍历的点y（dfn>x），那么一定会从他或者他祖先上的一个点走过去
//2）一定是先经过一段非树边（或者是LCA到LCA孩子的一小段）（即sdom），然后再随便走（树边或非树边）到d[p]
for(int p=pre[now];p!=-1;p=Next[p])
{
Set::Find(d[p]);//d[p]的祖宗最多有一个点dfn小于now，且min等于自己，所以是对的
//并查集min存的是他到祖宗路上sdom最小的点，是为了更新idom
if (dfn[sdom[Set::min[d[p]]]]<dfn[sdom[now]]) sdom[now]=sdom[Set::min[d[p]]];
}
Link(sdom_nex,sdom[now],now);//为了算支配点
Set::pa[now]=pa[now];//他的半支配点解决了，并到并查集里
now=pos[i-1];//此时sdom可能为now的点都解决了
for(int p=sdom_nex[now];p!=-1;p=Next[p])
{
Set::Find(d[p]);//此时d[p]的祖宗一定是now，min只会取到路径上点（也有可能取到now，不过此时sdom[now]=now），所以是对的
//https://blog.csdn.net/litble/article/details/83019578
if (sdom[Set::min[d[p]]]==now) idom[d[p]]=now;
//对于所有支配点，搜索树最深的支配点才是idom
//先考虑now是不是d[p]的支配点，如果now上面没有人可以不经过now到 now和d[p] 路径中的点（非now），那么now支配d[p]
else idom[d[p]]=Set::min[d[p]];
//如果now不是d[p]支配点，那么的下一个d[p]的可能支配点一定是now+->u ·->d[p]的sdom最小的那个u，然后在判断sdom[u]是不是u支配点
//这一过程可以理解为递归，然后相当与用idom记忆化 即idom[d[p]]=idom[min[d[p]]]
//又因为min[d[p]]小于now，所以先记下来然后填坑
}
}
For(i,2,n) if (idom[pos[i]]!=sdom[pos[i]]) idom[pos[i]]=idom[idom[pos[i]]];
For(i,2,n) Link(idom_nex,idom[i],i);
}
int ans[N];
void dfs_ans(int now)
{
ans[now]=1;
for(int p=idom_nex[now];p!=-1;p=Next[p]) dfs_ans(d[p]),ans[now]+=ans[d[p]];
}
int main()
{
// freopen("xx.in","r",stdin);
memset(nex,-1,sizeof(nex));memset(pre,-1,sizeof(pre));
memset(idom_nex,-1,sizeof(idom_nex));
memset(sdom_nex,-1,sizeof(sdom_nex));
read(n);read(m);
For(i,1,n) Set::min[i]=i,Set::pa[i]=i,sdom[i]=i;//dominate 主宰 这样初始化，保证答案正确性
For(i,1,m) read(x),read(y),Link(nex,x,y),Link(pre,y,x);
dfs(1);Tarjan();
dfs_ans(1);For(i,1,n) printf("%d ",ans[i]);
return 0;
}