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

# 支配树板子题 ## 简单介绍支配树 ### 1：定义 给定一个有向图(可以有环)，定下了一个节点为起点s。现在我们要求：从起点s出发，走向一个点t的所有路径中，必须要经过的点。 （换而言之就是如果删去该点，则s无法到达t） 则由支配点构成的树就是支配树了 ### 2：性质 （1）首先它是一颗树，边数为点数-1（废话） （2）在该树上，对于每个点p，p到根root所经过的点的集合就是它的支配点 （3）在该树上，对于每个点p，它是它的支配树上的子树内的点的必经点。 （4）若v,w是图中节点且dfn[v]<=dfn[w]，则任意从v到w的路径必然包含它们在dfs树中的一个公共祖先。 ## 支配树算法——Lengauer-Tarjan算法 由一般到特殊 如果这个有向图为一棵树，那么它本身便是一颗支配树（根据定义可知） 如果这个有向图无环（DAG），那么根据拓扑序，能到达该点的点在支配树中的LCA就是该点在支配树中的父亲节点（虽然有点绕，多读几遍就理解了） 推广至有向有环图 那么思路显然，牵扯到tarjan ### 几个重要变量 1：semi[x]:x的半支配点（简易来说，即x能够遍历的dfn大于x的点中的最小值） 2：idom[x]：x的支配点，即支配x的点中深度最大的点，是x在支配树上的父亲节点 性质： 1：每个点的半支配点是唯一的。 2：一个点的半支配点必定是它在dfs树上的祖先 3：x的半支配点**不一定**为x的支配点 4：semi[x]的深度大于等于idom[x]的深度 5：若节点U,V满足V在U到根节点的链上，则v在idom[U]到根节点的链上或者idom[U]在idom[v]到根节点的链上 ### 根据semi[x]求idom[x]： 令y= x到semi[x]路径上,dfn最小的点的编号 ``` if(semi[y]==semi[x]) idom[x]=semi[x] else idom[x]=idom[y] ``` ### 求取semi[x] 若x<y，则semi[y]=min(x)。 若x>y，则semi[y]=min({semi[z]|z>y且存在链z->y})。 ## 具体做法 1：对原图dfs，构建dfstree 2：计算半支配点 3：计算支配点 4：构建支配树 #### coding ``` #include<bits/stdc++.h> using namespace std; inline int read() { int x=0; char c=getchar(); bool flag=0; while(c<'0'||c>'9') {if(c=='-')flag=1;c=getchar();} while(c>='0'&&c<='9'){x=(x+(x<<2)<<1)+ c-'0';c=getchar();} return flag?-x:x; } const int N=2e5+5; int n,m; struct node { vector<int>edge[N]; inline void add(int u,int v){edge[u].push_back(v);} }a,b,c,d; int dfn[N],id[N],fa[N],cnt; void dfs(int u) { dfn[u]=++cnt;id[cnt]=u; int len=a.edge[u].size(); for(int i=0;i<len;++i) { int v=a.edge[u][i]; if(dfn[v])continue; fa[v]=u;dfs(v); } } int semi[N],idom[N],bel[N],val[N]; inline int find(int x) { if(x==bel[x])return x; int tmp=find(bel[x]); if(dfn[semi[val[bel[x]]]]<dfn[semi[val[x]]]) val[x]=val[bel[x]]; return bel[x]=tmp; } inline void tarjan() { for(int i=cnt;i>1;--i) { int u=id[i],len=b.edge[u].size(); for(int i=0;i<len;++i) { int v=b.edge[u][i]; if(!dfn[v])continue; find(v); if(dfn[semi[val[v]]]<dfn[semi[u]]) semi[u]=semi[val[v]]; } c.add(semi[u],u); bel[u]=fa[u]; u=fa[u]; len=c.edge[u].size(); for(int i=0;i<len;++i) { int v=c.edge[u][i]; find(v); if(semi[val[v]]==u)idom[v]=u; else idom[v]=val[v]; } } for(int i=2;i<=cnt;++i) { int u=id[i]; if(idom[u]!=semi[u]) idom[u]=idom[idom[u]]; } } int ans[N]; void dfs_ans(int u) { ans[u]=1; int len=d.edge[u].size(); for(int i=0;i<len;++i) { int v=d.edge[u][i]; dfs_ans(v); ans[u]+=ans[v]; } } int main() { n=read(),m=read(); for(int i=1;i<=m;++i) { int u=read(),v=read(); a.add(u,v); b.add(v,u); } for(int i=1;i<=n;++i) semi[i]=bel[i]=val[i]=i; dfs(1); tarjan(); for(int i=2;i<=n;++i) d.add(idom[i],i); dfs_ans(1); for(int i=1;i<=n;++i)printf("%d ",ans[i]); } ```