支配樹

其實還是一道支配樹板子題。。

最后在樹上dfs統計一下點到根的信息就行啦～

#include <bits/stdc++.h> #define INF 0x3f3f3f3f #define full(a, b) memset(a, b, sizeof a) using namespace std; typedef long long ll; inline int lowbit(int x){ return x & (-x); } inline int read(){int X = 0, w = 0; char ch = 0;while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();return w ? -X : X; } inline int gcd(int a, int b){ return a % b ? gcd(b, a % b) : b; } inline int lcm(int a, int b){ return a / gcd(a, b) * b; } template<typename T> inline T max(T x, T y, T z){ return max(max(x, y), z); } template<typename T> inline T min(T x, T y, T z){ return min(min(x, y), z); } template<typename A, typename B, typename C> inline A fpow(A x, B p, C lyd){A ans = 1;for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;return ans; } const int N = 50005; int n, m, k, dfn[N], fa[N], pos[N], parent[N], val[N], idom[N], sdom[N], size[N]; struct Graph{int cnt, head[N];struct Edge { int v, next; } edge[N<<2];void link(int a, int b){edge[cnt].v = b, edge[cnt].next = head[a], head[a] = cnt ++;} }a, b, c, d;void build(){k = a.cnt = b.cnt = c.cnt = d.cnt = 0;full(a.head, -1), full(b.head, -1), full(c.head, -1), full(d.head, -1);full(idom, 0), full(size, 0), full(pos, 0), full(fa, 0), full(dfn, 0);for(int i = 1; i <= n; i ++)parent[i] = sdom[i] = val[i] = i; }void dfs(int s){dfn[s] = ++k, pos[k] = s;for(int i = a.head[s]; i != -1; i = a.edge[i].next){int u = a.edge[i].v;if(!dfn[u]) fa[u] = s, dfs(u);} }int find(int s){if(s == parent[s]) return s;int tmp = find(parent[s]);if(dfn[sdom[val[parent[s]]]] < dfn[sdom[val[s]]]) val[s] = val[parent[s]];return parent[s] = tmp; }void tarjan(){for(int i = k; i > 1; i --){int s = pos[i];for(int j = b.head[s]; j != -1; j = b.edge[j].next){int u = b.edge[j].v;if(!dfn[u]) continue;find(u);if(dfn[sdom[val[u]]] < dfn[sdom[s]]) sdom[s] = sdom[val[u]];}c.link(sdom[s], s);parent[s] = fa[s], s = fa[s];for(int j = c.head[s]; j != -1; j = c.edge[j].next){int u = c.edge[j].v;find(u);if(sdom[val[u]] == s) idom[u] = s;else idom[u] = val[u];}}for(int i = 2; i <= k; i ++){int s = pos[i];if(idom[s] != sdom[s]) idom[s] = idom[idom[s]];} }void calc(int s){size[s] += s;for(int i = d.head[s]; i != -1; i = d.edge[i].next){int u = d.edge[i].v;if(!size[u]) size[u] += size[s], calc(u);} }void solve(){dfs(n), tarjan();for(int i = 1; i < n; i ++){if(idom[i]) d.link(idom[i], i);}calc(n); }int main(){while(cin >> n >> m){build();for(int i = 0; i < m; i ++){int u = read(), v = read();a.link(u, v), b.link(v, u);}solve();for(int i = 1; i <= n; i ++){printf("%d", dfn[i] ? size[i] : 0);if(i != n) printf(" ");}puts("");}return 0; }

轉載于:https://www.cnblogs.com/onionQAQ/p/10839603.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

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

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