支配树
nofind
·
·
个人记录
此处只记结论，证明可以见这篇博客。
一、问题：
给出一个有向图（可以有环），给定一个根root。
对于点对(x,y)，如果从root到y的每一条路径都过x，则称x支配y。设idom_x表示离x最近的支配x的点（支配点）。
显然除了根以外每个点x的idom_x是唯一的，从idom_x向x连边，会得到一棵树，从x的祖先都是x的支配点。
二、求解：
先从root出发求一颗dfs树，并求出每个点x的dfs序dfn_x。
定义半支配点sdom_x表示x的半支配点，其中sdom_x满足存在一条从sdom_x到x的路径，对于这条路径上的任意一点（不包括sdom_x和x）y都满足dfn_y>dfn_x，且sdom_x是满足这个性质的点中dfn最小的那个，显然sdom_x也是唯一的。
1.$sdom_x$是$x$的祖先。
2.$idom_x$是$x$的祖先。
3.$idom_x$是$sdom_x$的祖先。
如何求$sdom_x$：
对于每条边$(x,y)$：
$dfn_x<dfn_y$：如果$dfn_x<dfn_{sdom_y}$，那么$sdom_y=x$。
$dfn_x>dfn_y$: 找到$x$的祖先中$dfn$大于$dfn_y$且$dfn$最小的点$z$,用$sdom_z$更新$sdom_y$。
如何求$idom_x$：
我们可以用$sdom$推出$idom$。
1.如果$dfs$树上$sdom_x$到$x$的路径上（不包括$sdom_x$）的所有点$y$都满足$sdom_y\leqslant sdom_x$，那么$idom_x=sdom_x$。
2.不然找到$dfn_{sdom_y}$最小的点$y$，$idom_x=idom_y$。
### [模板题](https://www.luogu.com.cn/problem/P5180)
code:
```
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int n,m,tim;
int dfn[maxn],pos[maxn],sdom[maxn],idom[maxn],val[maxn],fa[maxn],bel[maxn];
vector<int>v1[maxn],v2[maxn],v3[maxn];
inline int read()
{
char c=getchar();int res=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();
return res*f;
}
void dfs_pre(int x)
{
dfn[x]=++tim;pos[tim]=x;
for(unsigned int i=0;i<v1[x].size();i++)
{
int y=v1[x][i];
if(dfn[y])continue;
dfs_pre(y);fa[y]=x;
}
}
inline int find(int x)
{
if(bel[x]==x)return x;
int y=find(bel[x]);
if(dfn[sdom[val[bel[x]]]]<dfn[sdom[val[x]]])val[x]=val[bel[x]];
return bel[x]=y;
}
inline void work()
{
for(int i=tim;i>=2;i--)
{
int x=pos[i];
for(unsigned int j=0;j<v2[x].size();j++)
{
int y=v2[x][j];
if(!dfn[y])continue;
find(y);
if(dfn[sdom[val[y]]]<dfn[sdom[x]])sdom[x]=sdom[val[y]];
}
v3[sdom[x]].push_back(x);bel[x]=fa[x];x=fa[x];
for(unsigned int j=0;j<v3[x].size();j++)
{
int y=v3[x][j];
find(y);
if(sdom[val[y]]==x)idom[y]=x;
else idom[y]=val[y];
}
}
for(int i=2;i<=tim;i++)
{
int x=pos[i];
if(idom[x]!=sdom[x])idom[x]=idom[idom[x]];
}
}
int cnt_edge;
int head[maxn],size[maxn];
struct edge{int to,nxt;}e[maxn];
inline void add_edge(int u,int v)
{
e[++cnt_edge].nxt=head[u];
head[u]=cnt_edge;
e[cnt_edge].to=v;
}
void dfs_ans(int x)
{
size[x]=1;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
dfs_ans(y);size[x]+=size[y];
}
}
int main()
{
n=read(),m=read();
for(int i=1;i<=m;i++)
{
int u=read(),v=read();
v1[u].push_back(v);v2[v].push_back(u);
}
for(int i=1;i<=n;i++)sdom[i]=bel[i]=val[i]=i;
dfs_pre(1);work();
for(int i=2;i<=n;i++)add_edge(idom[i],i);
dfs_ans(1);
for(int i=1;i<=n;i++)printf("%d ",size[i]);
return 0;
}
```