kkogoro

支配树(暂无证明)
支配树建法kkogoro并没有完全学会其中的证明步骤,所以证明先鸽了,但是文末给出了几个参考博客定义起点支配树(D...
扫描右侧二维码阅读全文
20
2019/03

支配树(暂无证明)

支配树建法

kkogoro并没有完全学会其中的证明步骤,所以证明先鸽了,但是文末给出了几个参考博客

定义

起点

支配树(Dominator Tree)是针对有向图建立的,我们给有向图指定一个起点 $r$ ,之后讨论的所有路径都是以 $r$ 为起点的

必经点

从 $r$ 出发走到达 $v$ 的任意路径上都会出现的点

支配点

$v$ 的所有必经点中离 $v$ 最近的一个点被称为 $v$ 的支配点(dominator),记作idom[v],我们也说idom[v]支配 $v$ 。特殊的,对起点 $r$ 不讨论支配点(但是要注意有时候题目中要求的必经点要包含点自身,就要计算一次)

支配树

每个点以自己的支配点作为父亲构成的树就是支配树

性质

支配树上一个点u是v的必经点当且仅当u在支配树上是v的祖先,每个点是且仅是其子树中的点的必经点

建立

特殊的图

对于拥有特殊性质的有向图,我们建立支配树有简单的方法

外向树

显然外向树就是其自身的支配树

DAG

对于有向无环图,所有有边指向点 $u$ 的点在支配树上的最近公共祖先就是 $u$ 的支配点,因此可以按照拓扑排序以及倍增动态加点LCA来在 $O((n+m)\log n)$ 复杂度内解决问题

普通有向图

咕咕咕咕咕咕咕,但是介绍一些概念

半必经点

求出dfs树后,设点 $s$ 满足从 $s$ 出发能找一条原图上的路径 $sp_{1}p_{2}\dots p_{k}t$ 满足所有的 $p$ 的dfn都比 $t$ 的大,而 $t$ 的半必经点(Semi Dominator)就是所有的 $s$ 中dfn最小的一个。

半必经点一定是 $t$ 的祖先。

求解

  • 概述

    • 求x的半必经点semi[x]: 对于原图上的边(y, x),如果dfn[y] < dfn[x],则y有潜力成为semi[x](也就是这样的 $y$ 是符合 $s$ 的定义的);如果dfn[y]>dfn[x],则y在dfs树上的祖先里满足dfn[z]>dfn[x]的点z的semi有潜力成为semi[x],而我们从这两部分点中选出一个dfn最小就是semi[x]
    • 求x的支配点idom[x]:设z是dfs树上semi[x]到x路径上(不含semi[x])semi的dfn最小的点,如果semi[x]=semi[z]则idom[x]=semi[x];否则idom[x]=idom[z]
  • 具体过程

    • 建立正反两图,初始化并查集,并把每个点的semi设为自己
    • 先以r为根进行dfs求出dfs树(只需标记father以及dfn与点的双射)
    • 按dfn大到小枚举每个点u,枚举反图u到达的每个点v,按照求semi的过程更新semi[u](注意dfn[v]=0的是不连通的点,要跳过)
    • 得到semi[u]后要记录semi[u]有一个u将其作为semi,将x加入并查集(并查集的fa[u]连向dfs树上的fa[u])
    • 每当处理完一个u后就处理dfn[u]-1对应的点p,枚举以p为semi的点q,根据idom求解过程更新idom[q]即可,但是要注意如果是semi[x] != semi[z]的情况就先把idom[q]标记为z,因为此时idom[z]还未被求出,全处理完之后更新一次idom!=semi的点就好(这样枚举是因为此时以p为semi的点到p的dfs树路径上(不含p)的点的semi都处理完了,这一点可以根据dfs树祖先dfn小于后代dfn以及semi[x]一定是x的祖先推出)
    • 根据idom数组建立支配树,进行树上统计
    • 查询x祖先中semi的dfn最小的点:根据dfs树祖先dfn小于后代dfn可以得到如果从大到小加入点,每个点向上的可供查询段一定是连续的(也就是以x为深度最大的点向上拓展若干个连续祖先),并且每次查询的点的dfn一定大于当前点(因为是按dfn从大到小处理的)。因为最小值信息是从底向根递增的,也就是新加入的点可以比之前的点更优,因此我们用带权并查集+路径压缩可以做到均摊 $O(\log n)$ 单次查询,每次压缩的时候自己与祖先取更优,但是要注意每次查询前都要压缩一次防止顶部有新加入的点导致答案改变。

细节

  • 需要注意在求semi和idom的过程中不需要对dfn最小的点(即起点r)求semi
  • 每个点的semi要初始化成自己
  • 注意连通性问题,从r出发无法到达的点没有支配点

例题

洛谷P5180

建立支配树后记录子树size即可

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>


inline int read() {
    int x = 0, f =  1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch =getchar();
    }
    return x * f;
}


const int MAXN = 200007;
const int MAXM = 300007;


struct Graph {
    int to[MAXM], nxt[MAXM], cntEdge, head[MAXN];
    inline void addEdge(const int &u, const int &v) {
        ++cntEdge;
        to[cntEdge] = v, nxt[cntEdge] = head[u], head[u] = cntEdge;
        return;
    }
} pre, bac, dom;


namespace DominatorTree {
    std::vector<int> semi_son[MAXN];
    int semi[MAXN], idom[MAXN], dfn[MAXN], dfs_fa[MAXN], time_stamp, id[MAXN];
    struct UNION {
        int fa[MAXN], min_anc[MAXN];
        int get(int x) {
            if (fa[x] == x) return x;
            int root = get(fa[x]);
            if (dfn[semi[min_anc[fa[x]]]] < dfn[semi[min_anc[x]]]) min_anc[x] = min_anc[fa[x]];
            return fa[x] = root;
        }
        inline void merge(int x, int y) {
            get(x), get(y);
            fa[x] = y;
            get(x);
            return;
        }
        inline void init(int n) {
            for (int i = 1; i <= n; ++i)
                fa[i] = min_anc[i] = i;
            return;
        }
    } uset;
    void dfs(int u) {
        dfn[u] = ++time_stamp;
        id[time_stamp] = u;
        for (int it = pre.head[u]; it != 0; it = pre.nxt[it]) {
            int v = pre.to[it];
            if (v != dfs_fa[u] && !dfn[v]) {
                dfs_fa[v] = u;
                dfs(v);
            }
        }
        return;
    }
    inline void getIdom(int n) {
        uset.init(n);
        dfs(1);
        for (int i = 1; i <= n; ++i) if (dfn[i]) semi[i] = i;
        for (int i = time_stamp; i > 1; --i) {
            int u = id[i], semi_dfn = n;
            for (int it = bac.head[u]; it != 0; it = bac.nxt[it]) {
                int v = bac.to[it];
                if (!dfn[v]) continue;
                else if (dfn[v] < dfn[u]) semi_dfn = std::min(semi_dfn, dfn[v]);
                else uset.get(v), semi_dfn = std::min(semi_dfn, dfn[semi[uset.min_anc[v]]]);
            }
            semi[u] = id[semi_dfn];
            uset.merge(u, dfs_fa[u]);
            semi_son[semi[u]].push_back(u);
            u = id[i - 1];
            for (std::vector<int>::iterator Iter = semi_son[u].begin(); Iter != semi_son[u].end(); ++Iter) {
                int v = *Iter;
                uset.get(v);
                if (semi[uset.min_anc[v]] == u) idom[v] = u;
                else idom[v] = uset.min_anc[v];
            }
        }
        for (int i = 2; i <= time_stamp; ++i) {
            int x = id[i];
            if (idom[x] != semi[x]) idom[x] = idom[idom[x]];
        }
        for (int i = 2; i <= n; ++i) {
            if (idom[i]) dom.addEdge(idom[i], i);
        }
        return;
    }
}


int size[MAXN];
void dfs_calc(int u, int fa) {
    size[u] = 1;
    for (int it = dom.head[u]; it != 0; it = dom.nxt[it]) {
        int v = dom.to[it];
        if (v == fa) continue;
        dfs_calc(v, u);
        size[u] += size[v];
    }
    return;
}


int main() {
    int n = read();
    int m = read();
    for (int i = 1; i <= m; ++i) {
        int u = read();
        int v = read();
        pre.addEdge(u, v);
        bac.addEdge(v, u);
    }
    DominatorTree::getIdom(n);    
    dfs_calc(1, -1);
    for (int i = 1; i <= n; ++i) printf("%d ", size[i]);
    return 0;
}

参考博客

支配树(dominator tree) 学习笔记@Fenghr

支配树速成记录@Kerry Su

支配树 与 tarjan算法@a710128

Last modification:March 21st, 2019 at 12:00 am

Leave a Comment