支配树学习笔记

· · 题解

支配树 学习笔记

给定一张有向图，设定源点为 s，则从 s 出发到 x 必须经过的点（不包括 x）称为支配点。（含不含自己影响不大，灵活处理就好）

若 a 支配 b，则 a 是 b 的支配点，在图中删去 a 点后不能从 s 到达 b。

支配关系是传递的、反对称的。

若 b 支配 a，且 c 支配 a，必然有 b 支配 c 或者 c 支配 b。显然一个点的所有支配点可以构成一个链，所有点与其最近支配点连线可以构成一个树。

以下的讨论建立在某一颗dfs树上。强烈建议阅读时自己画画草图示意。

定义 \operatorname{idom}_{x} 表示 x 的最近支配点， 也是深度最大的。定义 \operatorname{semi}_x 表示 x 的半支配点。半支配点 \operatorname{semi}_x 为 \operatorname{dfn} 最小的点 y，满足存在一条路径 (y,v_1,v_2,\cdots,v_c,x) 使得 \forall i\in\{1,2,\cdots,c\}，\operatorname{dfn}[v_i]> \operatorname{dfn}[x]。

#### 半支配点的性质： * 每个点的 $\operatorname{semi}$ 的唯一的。（ $\operatorname{dfn}$ 的有序性） * $\operatorname{semi}_x$ 是 $x$ 在dfs树上的祖先。 证明：首先证明 $\operatorname{dfn}[\operatorname{semi}_x]<\operatorname{dfn}[x]$。考虑一个点 $y$，$\operatorname{dfn}[y]>\operatorname{dfn}[x]$，存在一条满足条件的路径，那么 $y$ 的父节点也满足条件。如果父节点的 $\operatorname{dfn}$ 仍大于 $\operatorname{dfn}[x]$，重复找父节点即可。再证明，若 $\operatorname{dfn}[y]<\operatorname{dfn}[x]$ 且 $y$ 不是 $x$ 的祖先，一定不存在满足该条件的路径。反证法，若存在路径，则dfs过程中，$y$ 节点回溯前，已访问过 $x$，$x$ 在 $y$ 子树内。 * 如果有边 $(y,x)$，且 $\operatorname{dfn}[x]<\operatorname{dfn}[y]$，有 $\operatorname{dfn}[\operatorname{semi}_x]\le \operatorname{dfn}[\operatorname{semi}_y]$。 #### 半支配点和支配点的关系 * $\operatorname{semi}_x$ 不一定是 $\operatorname{idom}_x$。 * $\operatorname{idom}_x$ 在 $\operatorname{semi}_x$ （含）到根节点的链上。 * 利用 $\operatorname{semi}$ 求 $\operatorname{idom}$。（不然为什么引入半支配点的概念！） #### 如何求 $\operatorname{idom}$ ？ 在 dfs 树上，抽出 $\operatorname{semi}_x$ 到 $x$ 的链（不含端点）。 设其中 $z$ 点的 $\operatorname{semi}$ 的 $\operatorname{dfn}$ 最小。必有 $\operatorname{dfn}[\operatorname{semi}_z]\le \operatorname{dfn}[\operatorname{semi}_x]$ ，因为链上第一个点的 $\operatorname{semi}$ 只可能是 $\operatorname{semi}_x$ 及其祖先。 * 如果 $\operatorname{semi}_z = \operatorname{semi}_x$，那么 $\operatorname{idom}_x=\operatorname{semi}_x$。 * 如果 $\operatorname{dfn}[\operatorname{semi}_z]<\operatorname{dfn}[\operatorname{semi}_x]$，那么 $\operatorname{idom}_x=\operatorname{idom}_z$。 证明： 因为 $\operatorname{dfn}[\operatorname{semi}_z]<\operatorname{dfn}[\operatorname{semi}_x]$ ，所以从 $\operatorname{semi}_z$ 到 $z$ 不需要经过 $\operatorname{semi}_x$。$z$ 能到达 $x$，所以存在路径不经过 $\operatorname{semi}_x$，故 $\operatorname{semi}_x$ 不是 $x$ 的支配点。同理，从 $\operatorname{semi}_x$（含）到 $\operatorname{semi}_z$（不含）链上每一点都不是支配点。 此后，把 $\operatorname{semi}_x$ 到 $\operatorname{semi}_z$ 这段也抽出来考虑，重复上述过程。稍加思索归纳就会发现，对 $x$ 和 $z$ 的支配点产生影响的是同一条链，故 $\operatorname{idom}_x=\operatorname{idom}_z$。 #### 如何求 $\operatorname{semi}$ ？ 考虑有一条边（不是路径）$(y,x)$。 * 如果 $\operatorname{dfn}[y] < \operatorname{dfn}[x]$，$y$ 是它可能的半支配点。 * 如果 $\operatorname{dfn}[y] > \operatorname{dfn}[x]$，请上去回看一下含义，归结起来是 $y$ 到根链上所有 $\operatorname{dfn}$ 大于 $\operatorname{dfn}[x]$ 的点的 $\operatorname{semi}$ （这样能覆盖所有情况，而且也没有不符合的情况）。 #### 具体算法：Lengauer Tarjan ##### 求 $\operatorname{semi}

发现影响点 x 的，第一类直接更新，第二类都满足 \operatorname{dfn}[y]>\operatorname{dfn}[x]。

做法是逆着dfs序来，然后考虑完一个点，把它的 \operatorname{semi} 信息合并到他的父节点上。用带权并查集维护，每个点的权值为到根的路径上的min。

求 \operatorname{semi}_x 时，对于一条入边 (y,x) 且 \operatorname{dfn}[x]<\operatorname{dfn}[y] 的情况，查询 y 在并查集中的权。

求 \operatorname{idom}

求 \operatorname{idom} 时有操作是查询一条链上的最小 \operatorname{semi}，一个显然的思路是树剖... 但这样不优雅。发现可以用求 \operatorname{semi} 时的那个并查集来做。

当求 \operatorname{semi} 的过程推进到点 x 的 \operatorname{semi}_x 时，在并查集上求 x 的值就是求 x 到 \operatorname{semi}_x 这个链上最小值。故求 \operatorname{idom} 和求 \operatorname{semi} 同时进行，把求 \operatorname{idom}_x 这件事放到求 \operatorname{semi}_{\operatorname{semi}_x} 时。

具体看代码吧

#include <cstdio>
#include <queue>
int const maxn = 200003, maxm = 300003;

template<int N, int M>
struct Graph {
    int head[N], nxt[M], to[M], cnt;
    void insert(int u, int e) { nxt[++cnt] = head[u]; head[u] = cnt; to[cnt] = e; }
    void clear(int n) { cnt = 0; for (int i = 0; i <= n; ++i) head[i] = 0;}
};

int n = 0, m = 0;

Graph<maxn, maxm> G, F;
Graph<maxn, maxn> T;

int fa[maxn], dfn[maxn], idfn[maxn], cdfn = 0;
int semi[maxn], idom[maxn];

void dfs(int x) {
    dfn[x] = ++cdfn; idfn[cdfn] = x;
    for (int i = G.head[x]; i; i = G.nxt[i])
        if (!dfn[G.to[i]]) {
            fa[G.to[i]] = x;
            dfs(G.to[i]);
        }
}

inline int min_dfn(int x, int y) { return dfn[x] < dfn[y] ? x : y; }

namespace ADT {
    int fa[maxn], val[maxn];
    inline void init() {
        for (int i = 1; i <= n; ++i) fa[i] = i;
        // val is 0, and dfn[0] is put bigger than n.
    }
    int find(int x) {
        if (fa[x] == x) return x;
        int y = fa[x];
        fa[x] = find(fa[x]);
        if (dfn[semi[val[x]]] > dfn[semi[val[y]]]) val[x] = val[y];
        return fa[x];
    }
    inline void merge(int x, int y) { // x <-- y
        x = find(x); y = find(y);
        fa[y] = x;
    }
};

int deg[maxn], siz[maxn];

int main() {
    scanf("%d %d", &n, &m);
    int x = 0, y = 0;
    for (int i = 1; i <= m; ++i) {
        scanf("%d %d", &x, &y);
        G.insert(x, y);
        F.insert(y, x);
    }

    dfs(1);
    dfn[0] = n + 1; // prepare for comparation
    ADT::init();

    for (int i = n; i >= 1; --i) {
        x = idfn[i];
        for (int j = F.head[x]; j; j = F.nxt[j]) { // get semi[x]
            y = F.to[j];
            if (dfn[y] < dfn[x]) semi[x] = min_dfn(semi[x], y);
            else {
                ADT::find(y);
                semi[x] = min_dfn(semi[x], semi[ADT::val[y]]);
            }
        }
        for (int j = T.head[x]; j; j = T.nxt[j]) { // work for the "y"s which semi[y] = x
            y = T.to[j];
            ADT::find(y);
            int z = ADT::val[y];
            if (dfn[semi[z]] == dfn[x]) idom[y] = x; // equal to idom[y]=semi[y]
            else idom[y] = z; // coorect later
        }

        ADT::val[x] = x;
        ADT::merge(fa[x], x);
        T.insert(semi[x], x); // a query.
    }
    for (int i = 2; i <= n; ++i) {
        x = idfn[i];
        if (idom[x] != semi[x]) idom[x] = idom[idom[x]];
    }

    for (int i = n; i >= 1; --i) {
        x = idfn[i];
        ++siz[x];
        if (idom[x]) siz[idom[x]] += siz[x];
    }

    for (int i = 1; i <= n; ++i) printf("%d ", siz[i]);
    return 0;
}