【算法】支配树

采用 $\text{CC BY-NC-SA 4.0}$ 许可，转载请注明：“转自【算法】支配树”

前言

本文章取材自此篇博客，以及李煜东的《图连通性若干问题探讨》。
由于支配树的 $Lengauer-Tarjan$ 算法涉及到较多性质和引理的证明，容易遗忘，所以作者在这里把证明的大致框架整理出来。
在下文中，不妨对图重标号，使得 $u=dfn_u$ —— 即下文中，对两个点进行比较实质上是对其 dfs序进行比较。

支配树

流图 (Flow Graph)：若有向图 $G$ 中存在一点 $r$，从 $r$ 出发可以到达 $G$ 中所有的点，则称 $G$ 是 Flow Graph，记为 $(G,r)$。
对图中的边 $\langle u, v \rangle$ 进行分类：
1. 树边： $u<v$
2. 前向边： $u<v$
3. 后向边： $u>v$
4. 横叉边： $u>v$
支配点：若在 $(G,r)$ 中从 $r$ 到 $u$ 的路径一定经过点 $v$ ，则称 $v$ 是 $u$ 的支配点，记为$v\ dom\ u$。
最近支配点：节点 $u$ 的必经点集合 $dom(u)$ 中，除点 $u$ 外，被所有其它点支配的点 $v$，称作 $u$ 的最近支配点，记作 $idom(u)$。
- 定理1：除了源点的点均存在唯一的最近支配点。
支配树：每个点向其最近支配点连边，得到的树。

DAG 的支配树求解

记点 $u$ 的前驱节点集合为 $prev(u)$，则 $dom(u) = {u} \cup \bigcap_{w\in prev(u)}{dom(w)}$
在 DAG 中，按照拓扑序求解；根据上式，每个点的 $idom$ 为其所有前驱的 $idom$ 的 LCA。
- 复杂度 $O(mlogn)$。
在有环图中，可以每次删掉一个点，跑一遍 dfs，记录哪些点变得不可达，以求出其支配点集合。
- 复杂度 $O(nm)$。

L-T 算法

定义：半支配点：对于 $u \ne r$，定义其半支配点为

$sdom(u) = min\{w|\exists(v_0, ..., v_k), k \ge 1 , v_0 = w, v_k = u, \forall 1\leq i< k, v_i>u \}$

- 即：只经过 $>u$ 的点可以到达点 $u$ 的所有点中的最小点。
引理1（路径引理）：如果两个点 $u, v$ 满足 $u < v$，则任意从 $u$ 到 $v$ 的路径经过它们的公共祖先。
- 证明：如果不能经过公共祖先，可用的边就只剩下横叉边；但横叉边一定是从大到小，矛盾。
引理2：$idom(u)$ 是 $u$ 的祖先，即 $ idom(u) \in asc(u) $。
引理3：$sdom(u)$ 是 $u$ 的祖先。由引理1可证。
引理4：$idom(u)$ 是 $sdom(u)$ 的祖先，或二者相等。
引理5：任意 $idom(u)$ 到 $u$ 的路径两两不交（于非端点的点）。
定理2：若对所有满足 $u \leq w < sdom(u)$ 且 $sdom(u) \in asc(w) $ 的点 $w$，均有：
- 由引理4可证。
定理3：若对最小的满足 $u \leq w < sdom(u)$ 且 $sdom(u) \in asc(w) $ 的点 $w$，均有：
- 由引理4, 5可证
推论（必经点定理）：对最小的满足 $u \leq w < sdom(u)$ 且 $sdom(u)$ 是 $w$ 的祖先的点 $w$，有：
$idom(u)= \begin{cases} sdom(u), &sdom(w) = sdom(u)\\ idom(w), &sdom(w) < sdom(u) \end{cases}$
定理4（半必经点定理）：

$\begin{array}{cc} sdom(u) = \min \{ w|w\in prev(u), w < u \} \cup \\ \{ sdom(v)|w \in prev(u), w > v > u, v \in asc(w) \} \end{array}$
- PPT中的表述如下：
  
  对于𝐺中的一点𝑦，考虑所有𝑥∈𝑝𝑟𝑒(𝑦)，定义一个临时变量𝑡𝑒𝑚𝑝=+INF。
  若𝑑𝑓𝑛[𝑥]<𝑑𝑓𝑛[𝑦]，𝑡𝑒𝑚𝑝=min(𝑡𝑒𝑚𝑝,𝑑𝑓𝑛[𝑥])。
  若𝑑𝑓𝑛[𝑥]>𝑑𝑓𝑛[𝑦]，对任意𝑥在𝑇中的祖先𝑧，满足𝑑𝑓𝑛[𝑧]>𝑑𝑓𝑛[𝑦]时，
  有𝑡𝑒𝑚𝑝=min(𝑡𝑒𝑚𝑝,𝑑𝑓𝑛[𝑠𝑒𝑚𝑖[𝑧]])。
  𝑠𝑒𝑚𝑖[𝑦]=𝑖𝑑[𝑡𝑒𝑚𝑝]。即在上述所有可能情况中取𝑑𝑓𝑛值最小的一种，就是𝑦的半必经点。

代码实现

有了必经点定理和半必经点定理，就可以进行代码实现了。流程大致如下：
1. 处理出 DFS 树；
2. 利用半必经点定理，按照 DFS序的逆序求出每个点的 sdom；
3. 利用必经点定理，求出 idom == sdom 的点；
4. 由第 3 步中的 idom 求出所有点的 idom。
代码实现细节如下：
1. 将每个点的 sdom 初始化为自身。
2. 在第 2 步中，对每个点维护 home 值，表示半必经点定理中满足要求的 sdom 最小值点。
3. 利用带权并查集算法，按dfs序的逆序每次将某点与父节点合并，以处理半必经点定理中 $v > u $ 的限制，同时维护 home 值（值为该点到其集合的根节点路径上 sdom 最小者）。
4. 第 2, 3 步一并处理的过程中，将每个点的 home 值（查询结果）临时记录到 idom 中，以便下一步使用。
5. 由于我们记录的是 sdom(u) 的最小值点而非最小值，所以算法第 4 步中，应当判断二者的 sdom 之间的大小关系，而非比较本身的大小关系（见代码）。
算法复杂度$O(N\log N)$。

代码

HDU4694: Important Sisters

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, m, S;
int dfn[N], ID[N], fa[N], timer;
int p[N], semi[N], idom[N], home[N];
vector <int> E[N], E_rev[N], Vs[N];
int res[N];



int find(int x) {
    if(p[x] < 0) return x;
    int px = find(p[x]);
    home[x] = getmin(home[x], home[p[x]]);
    return p[x] = px;
}

inline void onion(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return ;
    home[x] = getmin(home[x], home[y]);
    p[x] = y;
}

void dfs(int u, int pre) {
    dfn[u] = ++timer;
    ID[timer] = u;
    fa[u] = pre;
    for(auto v: E[u]) if(dfn[v] == 0) dfs(v, u);
}

void clear() {
    for(int i = 1; i <= n; i++) {
        E[i].clear();
        E_rev[i].clear();
        Vs[i].clear();
        idom[i] = fa[i] = home[i] = 0;
    }
}



void init() {
    int u, v;
    for(int i = 1; i <= m; i++) {
        scanf("%d%d", &u, &v);
        E[u].push_back(v);
        E_rev[v].push_back(u);
    }
    S = n;
    timer = 0;
    for(int i = 1; i <= n; i++) dfn[i] = 0, p[i] = -1, semi[i] = home[i] = i;
    dfs(S, 0);
    for(int i = timer; i >= 2; i--) {
        u = ID[i];
        for(auto v: E_rev[u])
            if(dfn[v]) semi[u] = semi[getmin(u, gethome(v))]; //key1 注意这里的写法
        Vs[semi[u]].push_back(u);
        for(auto v: Vs[fa[u]]) idom[v] = gethome(v); //key2
        Vs[fa[u]].clear();
        onion(u, fa[u]);
    }
    res[S] = S;
    for(int i = 2; i <= timer; i++) {
        u = ID[i];
        if(semi[idom[u]] == semi[u]) idom[u] = semi[u]; //key3 注意是semi相等，不一定是idom[u]==u
        else idom[u] = idom[idom[u]]; //key4
        res[u] = res[idom[u]] + u;
    }
    for(int i = 1; i <= n; i++) {
        if(dfn[i] == 0) printf("0");
        else printf("%d", res[i]); 
        if(i == n) printf("\n");
        else printf(" ");
    }
    clear();
}

int main() {
    while(scanf("%d%d", &n, &m) != EOF) init();
    return 0;
}

Author : Fanfaredash

前言

支配树

DAG 的支配树求解

L-T 算法

代码实现

代码

CATALOG

FRIENDS