支配树

本文主要是介绍支配树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

入门版 （DAG图）

洛谷 P2597 [ZJOI2012]灾难

https://www.luogu.org/problem/P2597

给的图为DAG图 建反向图 通过反向图将有多个父亲的点 求所有父亲的LCA 将改点连在LCA上。

#include <bits/stdc++.h>using namespace std;
const int maxn = 1e5+10;
vector<int> G[maxn]; 
vector<int> E[maxn];
vector<int> T[maxn]; //G原图 E反图 T支配树
int fa[maxn][20],deep[maxn];
int dfn[maxn],in[maxn];
int n,m;
int ans[maxn];
void init()
{memset(in,0,sizeof(in));for(int i = 0;i <= n;i++){E[i].clear(),G[i].clear(),T[i].clear();}
}
int LCA(int u,int v)
{if(deep[u] < deep[v]) swap(u,v);for(int i = 18;i >= 0;i--){if(deep[fa[u][i]] >= deep[v])u = fa[u][i];}if(u == v) return u;for(int i = 18;i >= 0;i--){if(fa[u][i] != fa[v][i]){u = fa[u][i];v = fa[v][i];}}return fa[u][0];
}
void solve(int u)
{int x = G[u][0];for(int i = 1;i < G[u].size();i++){x = LCA(x,G[u][i]);}T[x].push_back(u);deep[u] = deep[x]+1;fa[u][0] = x;for(int j = 1;j <= 18;j++){fa[u][j] = fa[fa[u][j-1]][j-1];}
}
void topsort()
{for(int i = 1;i <= n;i++){if(in[i] == 0){G[i].push_back(0);E[0].push_back(i);}}queue<int> q;q.push(0);deep[0] = 0;while(!q.empty()){int x = q.front();q.pop();for(int i = 0;i < E[x].size();i++){int y = E[x][i];in[y]--;if(in[y]<= 0){q.push(y);solve(y);}}}
}
void dfs(int u) //
{}int main()
{scanf("%d%d",&n,&m);init();for(int i = 1; i <= m; i++){int u,v;scanf("%d%d",&u,&v);in[u]++;E[v].push_back(u);G[u].push_back(v);}topsort();dfs(0,1);return 0;
}

进阶版 （有环图）

P5180 【模板】支配树

https://www.luogu.org/problem/P5180

先建DAG图

#include <bits/stdc++.h>using namespace std;
const int maxn = 3e5 + 10;
int n,m,ans[maxn];
int dfn[maxn],id[maxn],tot,dep[maxn];
int idom[maxn],semi[maxn],mn[maxn],in[maxn],f[maxn][20];
int fa[maxn]; //权值线段树
int q[maxn],top;
queue<int> Q;
vector<int> A[maxn],rA[maxn],B[maxn],rB[maxn],C[maxn]; //A原图 rA原图反图 B为DAG图 rB为DAG图反图 C支配树
void init()
{top = tot = 0;for(int i = 1;i <= n;i++){A[i].clear(),rA[i].clear(),B[i].clear(),rB[i].clear(),C[i].clear();dfn[i] = id[i] = ans[i] = in[i] = idom[i] = dep[i] = 0;fa[i] = mn[i] = semi[i] = i;for(int j = 0;j <= 18;j++) f[i][j] = 0;}
}
void dfs(int u,int fa)
{dfn[u] = ++tot;id[tot] = u;idom[u] = fa;B[fa].push_back(u);for(int i = 0;i < A[u].size();i++){int v = A[u][i];if(dfn[v] == 0){dfs(v,u);}}
}
int LCA(int u,int v)
{if(dep[u] < dep[v]) swap(u,v);for(int i = 18;i >= 0;i--){if(dep[f[u][i]] >= dep[v])u = f[u][i];}if(u == v) return u;for(int i = 18;i >= 0;i--){if(f[u][i] != f[v][i]){u = f[u][i];v = f[v][i];}}return f[u][0];
}int fin(int x)
{if(x == fa[x]) return x;int tmp = fa[x];fa[x] =fin(fa[x]);if(dfn[semi[mn[tmp]]] < dfn[semi[mn[x]]]) mn[x] = mn[tmp];return fa[x];
}
void Work()
{dfs(1,0);for(int i = n;i >= 2;i--){int x = id[i],res = n;if(!x) continue;for(int j = 0;j < rA[x].size();j++){int y = rA[x][j];if(dfn[y]==0) continue;if(dfn[y] < dfn[x]) res = min(res,dfn[y]);else{fin(y);res = min(res,dfn[semi[mn[y]]]);}}semi[x] = id[res],fa[x] = idom[x],B[semi[x]].push_back(x);}for(int i = 1;i <= n;i++){for(int j = 0;j < B[i].size();j++){int x = B[i][j];in[x]++;rB[x].push_back(i);}}//for(int x = 1;x <= n;x++){if(!in[x]) Q.push(x);}while(!Q.empty()){int u = Q.front();Q.pop();q[++top] = u;for(int i = 0;i < B[u].size();i++){int v = B[u][i];in[v]--;if(in[v] <= 0){Q.push(v);}}}for(int i = 1;i <= top;i++){int u = q[i];int x = 0;if(rB[u].size() != 0)x = rB[u][0];for(int j = 1;j < rB[u].size();j++){x = LCA(x,rB[u][j]);}f[u][0] = x;dep[u] = dep[x] + 1;C[x].push_back(u);for(int j = 1;j <= 18;j++){f[u][j] = f[f[u][j-1]][j-1];}}ans[0] = 0;}
void dfsans(int u)
{ans[u] = 1;for(int i = 0;i < C[u].size();i++){int v = C[u][i];dfsans(v);ans[u] += ans[v];}
}
int main()
{scanf("%d%d",&n,&m);init();for(int i = 1;i <= m;i++){int x,y;scanf("%d%d",&x,&y);A[x].push_back(y);rA[y].push_back(x);}Work();dfsans(1);for(int i = 1;i <= n;i++){printf("%d ",ans[i]);}
}

 

这篇关于支配树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---