HDU4694 Important Sisters

支配树

其实还是一道支配树板子题。。

最后在树上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;
}