Bookmarks

You haven't yet saved any bookmarks. To bookmark a post, just click .

  • 被树支配的恐惧

  • 前言

    你敢信你有生之年还会被树支配上几次?反正我是被支配了……

    支配树解决的是一个很现实的问题:假设S给T通过各种途径提供生(mo)命(fa)之源,但这些途径都有一个共性(都经过一个点),现在你想用最小的代价(摧毁尽可能少的点)抹除T,那么你应该摧毁哪些点

    概念

    给定一个有向图,给定起点S,终点T,在所有从S到T的路径中,如果删去某个点,则不存在一条路径能够使S到达T,则这个点被称为支配点。由支配点构成的树叫做支配树。支配树是一颗由起点S为根的树,根到树上任意一点路径经过的点都是它的支配点。

    一张有向图

    主要变量

    dfn[x],表示dfs序

    id[x], 表示dfs序对应的点

    dfa[x], 第一遍dfs中,每个点的父节点

    sdom[x], x的半支配点

    idom[x], x的支配点

    fa[x], 并查集(都懂)

    mindfn[x],从x到其已经被搜过的祖先的dfn的最小值

    半支配点的定义(tarjan tql)

    性质(证明略)

    1:半支配点是唯一的(但是支配点可以有多个)

    2:对于任意点w,它的半支配点必定是它在dfs\ tree上的祖先

    3:对于任意节点w != s, w的支配点必然是该节点的半支配点的祖先节点

    4:假设 存在v,w且v是w的祖先,那么idom[w]要么是v的后代,要么是idom[v]的祖先。

    求sdom的方法(伪代码)

    for_each k in G with cond (dfn[k]>dfn[u] && k.canreach(u))
    if(dfn[u]>dfn[v]) 
        sdom[u]=mindfn(v);
    else 
        sdom[u]=mindfn{sdom[k]}
    

    求idom的方法

    如果图中存在节点v,w,且v支配w,并且w的其他支配点均支配v,我们就称v是w的最近支配点,记作idom[w]=v

    (仍然是伪代码)

    def P = {all vertex U on route x->sdom[x]}
    for_each k=min(dfn[P[i]])
    if(sdom[k]==sdom[x])
        idom[x]=sdom[x]
    else 
        idom[x]=idom[z]
    

    总体步骤

    1:对这张图进行一遍dfs,求出dfn

    2:根据dfn大小从大到小遍历求出sdom

    3:保留dfs树上的节点和边,求出该点祖先链中sdom的最小值mindfn[v],然后这个点会成为一颗子树的根,通过带权并查集维护各个子树并连接。通过sdom求出idom

    模板

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

    给定一张有向图,求从1号点出发,每个点能支配的点的个数

    #include <bits/stdc++.h>
    
    using namespace std;
    
    static constexpr int maxn = 300050;
    
    struct node {
        vector<int> e[maxn];
        inline void add(int u, int v) { e[u].push_back(v); }
    } a, b, c, d;
    
    int dfn[maxn], id[maxn], dfa[maxn], sdom[maxn], idom[maxn], fa[maxn],
        mindfn[maxn], cnt;
    
    void dfs(int u) {
        dfn[u] = ++cnt;
        id[cnt] = u;
        for (int i : a.e[u]) {
            if (dfn[i]) {
                continue;
            }
            dfa[i] = u;
            dfs(i);
        }
    }
    
    int find(int x) {
        if (x == fa[x]) {
            return x;
        }
        int tmp = find(fa[x]);
        if (dfn[sdom[mindfn[fa[x]]]] < dfn[sdom[mindfn[x]]]) {
            mindfn[x] = mindfn[fa[x]];
        }
        return fa[x] = tmp;
    }
    
    void zp() {
        for (int i = cnt; i > 1; i--) {
            int u = id[i];
            for (int v : b.e[u]) {
                if (!dfn[v]) {
                    continue;
                }
                find(v);
                if (dfn[sdom[mindfn[v]]] < dfn[sdom[u]]) {
                    sdom[u] = sdom[mindfn[v]];
                }
            }
            c.add(sdom[u], u);
            fa[u] = dfa[u];
            u = fa[u];
            for (int v : c.e[u]) {
                find(v);
                sdom[mindfn[v]] == u ? idom[v] = u : idom[v] = mindfn[v];
            }
        }
        for (int i = 2; i <= cnt; i++) {
            int u = id[i];
            if (idom[u] != sdom[u]) {
                idom[u] = idom[idom[u]];
            }
        }
    }
    
    void zp_write(int n) {
        for (int i = 2; i <= n; i++) {
            d.add(idom[i], i);
        }
    }
    
    int ans[maxn];
    
    void dfs2(int u) {
        ans[u] = 1;
        for (int i : d.e[u]) {
            dfs2(i);
            ans[u] += ans[i];
        }
    }
    
    int main() {
        int n, m;
        cin >> n >> m;
        int u, v;
        for (int i = 1; i <= m; i++) {
            cin >> u >> v;
            a.add(u, v);
            b.add(v, u);
        }
        for (int i = 1; i <= n; i++) {
            sdom[i] = fa[i] = mindfn[i] = i;
        }
        dfs(1);
        zp();
        zp_write(n);
        dfs2(1);
        for (int i = 1; i <= n; i++) {
            cout << ans[i] << " ";
        }
        cout << endl;
        return 0;
    }