????對于有向無環圖的支配樹
????按照拓撲排序建樹
????每個節點在支配樹上的父親
????是原圖上所有父親的 $LCA$
????時間復雜度：$O(nlogn)$

????$DAG$ 支配樹模板題：滅絕樹~~~~

---

DAG支配樹模板

#include<bits/stdc++.h> #define rint register int #define deb(x) cerr<<#x<<" = "<<(x)<<'\n'; using namespace std; typedef long long ll; typedef pair <int,int> pii; const ll mod = 1e9 + 7; const int maxn = 5e4 + 10; int n, m, cnt, ans[maxn]; int in[maxn], tp[maxn]; int f[maxn][25], dep[maxn]; vector <int> g[maxn]; vector <int> t[maxn], fa[maxn];int lca(int x, int y){if(dep[x] < dep[y]) swap(x, y);for(int i=20; ~i; i--)if(dep[f[x][i]] >= dep[y])x = f[x][i];if(x == y) return x;for(int i=20; ~i; i--)if(f[x][i] ^ f[y][i])x=f[x][i], y=f[y][i];return f[x][0]; }void build(int x){int lcaf = fa[x][0];for(int i=1; i<fa[x].size(); i++)lcaf = lca(lcaf, fa[x][i]);t[lcaf].push_back(x);dep[x] = dep[lcaf] + 1;f[x][0] = lcaf;for(int i=1; i<=20; i++)f[x][i] = f[f[x][i-1]][i-1]; }void tp_sort(){queue <int> Q;for(int i=1; i<=n; i++)if(!in[i]) {in[i]++;g[0].push_back(i);fa[i].push_back(0);} Q.push(0);while(!Q.empty()){int q = Q.front();Q.pop();tp[cnt++] = q;for(auto i : g[q]){in[i]--;if(!in[i]) {Q.push(i);build(i);}}} }void dfs(int x){ans[x] = 1;for(auto i : t[x]){dfs(i);ans[x] += ans[i];} }int main() {scanf("%d", &n);for(int i=1, x; i<=n; i++){while(1){scanf("%d", &x);if(x==0) break;g[x].push_back(i);fa[i].push_back(x);in[i]++;}}tp_sort();dfs(0); for(int i=1; i<=n; i++) printf("%d\n", ans[i]-1); }

總結

以上是生活随笔為你收集整理的DAG支配树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。