支配树

What · 是什么

支配树(Dominator Tree)用于描述有向图中'从入口s出发到某点的所有路径都必须经过哪些点'的支配关系。若从s到u的每条路径都经过v，则称v支配u。支配关系满足树形结构：每个节点(除s外)恰有一个直接支配者idom(u)，把所有idom边连起来就得到以s为根的支配树。在支配树上，v支配u当且仅当v是u的祖先。求解支配树的经典算法是Lengauer-Tarjan算法，复杂度O((E+V)α(V))，通过半支配点(semi-dominator)间接求直接支配者。对DAG有更简单的拓扑序+倍增LCA解法，对树则支配树就是它本身。典型应用：ZJOI2012灾难(灭绝树)、程序控制流图分析、统计每个点被哪些点必经支配。

Why · 为什么

How · 实现

伪代码

# Lengauer-Tarjan 框架
dfs(s):   # 建DFS树, 记录dfn/pos/fth
  dfn[u]=++dfc; pos[dfc]=u
  for v in out[u]: if not dfn[v]: dfs(v); fth[v]=u

# 带权并查集 find(x): 返回sdm最小的节点mn[x]
# 阶段1: 算sdm (按dfc从大到小)
for i in dfc..2:
  u=pos[i]
  res=dfn[u]
  for v in in[u]:            # 入边
    if dfn[v]==0: continue
    find(v)
    if dfn[v]<dfn[u]: res=min(res, dfn[v])
    else: res=min(res, dfn[sdm[mn[v]]])
  sdm[u]=pos[res]
  fa[u]=fth[u]               # 并查集挂到父节点
  # 阶段2(内联): 对挂在sdm[u]下的v: idom[v]=sdm[v]或mn[v]
# 阶段3: 修正
for i in 2..dfc:
  u=pos[i]
  if idom[u]!=sdm[u]: idom[u]=idom[idom[u]]
# 支配树边: (idom[u], u)

Python 实现

# DAG上的支配树: 拓扑序+倍增LCA (P2597灾难的解法)
import sys
from collections import deque

sys.setrecursionlimit(1 << 25)


def dominator_tree_dag(n, s, edges):
    """DAG的支配树.
    n: 节点数, s: 唯一入口(1-based), edges: [(u,v),...]
    返回: idom数组(1-based, idom[s]=s), 支配树上父节点
    """
    g = [[] for _ in range(n + 1)]
    rg = [[] for _ in range(n + 1)]
    indeg = [0] * (n + 1)
    for u, v in edges:
        g[u].append(v)
        rg[v].append(u)
        indeg[v] += 1

    # 拓扑序
    q = deque([s])
    topo = []
    indeg_saved = indeg[:]
    while q:
        u = q.popleft()
        topo.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)

    LOG = (n + 1).bit_length()
    up = [[0] * (n + 1) for _ in range(LOG)]  # 支配树倍增祖先
    dep = [0] * (n + 1)
    idom = [0] * (n + 1)
    idom[s] = s

    def lca(u, v):
        if dep[u] < dep[v]:
            u, v = v, u
        d = dep[u] - dep[v]
        k = 0
        while d:
            if d & 1:
                u = up[k][u]
            d >>= 1
            k += 1
        if u == v:
            return u
        for k in range(LOG - 1, -1, -1):
            if up[k][u] != up[k][v]:
                u = up[k][u]
                v = up[k][v]
        return up[0][u]

    # 按拓扑序: idom[u] = 所有前驱在支配树上的LCA
    for u in topo:
        if u == s:
            continue
        if not rg[u]:
            continue
        anc = rg[u][0]
        for v in rg[u][1:]:
            anc = lca(anc, v)
        idom[u] = anc
        up[0][u] = anc
        dep[u] = dep[anc] + 1
        for k in range(1, LOG):
            up[k][u] = up[k - 1][up[k - 1][u]]
    return idom


if __name__ == "__main__":
    # 测试DAG: s=1, 1->2, 1->3, 2->4, 3->4, 4->5
    # 支配: 1支配全部; 4支配5; idom: 2<-1,3<-1,4<-1,5<-4
    edges = [(1, 2), (1, 3), (2, 4), (3, 4), (4, 5)]
    idom = dominator_tree_dag(5, 1, edges)
    assert idom[1:] == [1, 1, 1, 1, 4], idom

    # 测试链: 1->2->3->4, idom为直接前驱
    edges2 = [(1, 2), (2, 3), (3, 4)]
    idom2 = dominator_tree_dag(4, 1, edges2)
    assert idom2[1:] == [1, 1, 2, 3], idom2

    # 测试分支再汇合: 1->2,1->3,2->4,3->4, 4的前驱2,3的LCA=1
    edges3 = [(1, 2), (1, 3), (2, 4), (3, 4)]
    idom3 = dominator_tree_dag(4, 1, edges3)
    assert idom3[1:] == [1, 1, 1, 1], idom3

    print("dominator-tree(DAG): ALL TESTS PASSED")

易错点

• 支配树要求唯一入口，多入口需虚拟超级源点处理
• sdom与idom的修正公式容易记错：先算sdom, 再通过路径上sdom最小节点v判断idom=sdom(u)或idom(v)
• 带权并查集find的路径压缩必须维护mn(半支配点最小节点), 不是只维护并查集根
• DAG特例中所有前驱的LCA即为idom，但前提是DAG连通且单源
• 图不连通时，无法到达的节点没有支配关系，需单独讨论

例题

信源

• OI Wiki✓ https://oi-wiki.org/graph/dominator-tree/
• Wikipedia✓ https://en.wikipedia.org/wiki/Dominator_(graph_theory)