算法 - 支配树 (Lengauer Tarjan)

Posted on Edited on In Disqus:

对于有向图 $G$（可能有环），其中起点 $r$ 可以到达所有点，当 $u$ 是所有到达 $v$ 的路径的必经点时，称 $u$ 支配 $v$。

可以构建支配树，其中每个点被所有它的祖先支配，又支配它子树中的结点。

半必经点

考虑 $G$ 的搜索树，定义 $semi(x)$ 是 ${u | \text{存在} dfn[p_i]>dfn[x] \text{ 使得 } u,p_1,p_2,\dots, p_k, x \text{ 是一条路径}}$ 中 $dfn$ 最小的点。

不严谨地说，$semi(x)​$ 就是 $x​$ 的祖先 $z​$ 中，能不经过 $z​$ 和 $x​$ 之间的树上的点而到达 $x​$ 的点中深度最小的。

性质

  • $semi(x)$ 一定是 $x$ 的祖先
    • 首先 $semi(x)$ 深度肯定比 $fa(x)$ 小
    • 如果 $semi(x)$ 和 $x$ 在 $u$ 的不同子树中，$u$ 的深度肯定比 $semi(x)$ 小且符合 $semi(x)$ 的定义
  • 半必经点不一定是必经点
    • 考虑一下，半必经点如果能被绕过的话就不是必经点了
  • 对于所有 $(u,x) \in E$
    • $u<x$，也就是树边或者前向边，此时有 $semi(x) \leq u$，也就是路径 $u \rightarrow x$。
    • $u > x$，也就是后向边或者横叉边，对于所有满足 $v > x$ 的 $u$ 的祖先 $v$，有 $semi(x) \le semi(v)$，也就是路径 $semi(v) \rightarrow v \rightarrow u \rightarrow x$。
    • 这样就考虑了 $semi(x) \rightarrow x$ 的最后一条边的所有可能。

必经点

定义 $idom(x)$ 是所有支配 $x$ 的点中深度最大的。

性质

  • $idom(x)$ 的深度不大于 $semi(x)$
    • 如果拆掉的点深度大于 $semi(x)$，那么可以通过路径 $r \rightarrow semi(x) \rightarrow x$ 来绕过。
  • 设点集 $P$ 是 $semi(x)$（不包括） 到 $x$ 路径上经过的点，$t$ 是点集 $P$ 中 $semi$ 最小的点。
    • 如果 $semi(x)=semi(t)$，那么 $idom(x) = semi(x)$。
      • 只需证明 $semi(x)$ 是 $x$ 的必经点。用力感受一下，如果能绕过 $semi(x)$ 的话，肯定会先跳到点集 $P$ 中。
    • 如果 $semi(x) \ne semi(t)$，那么 $idom(x) = idom(t)$。
      • 首先证明 $idom(t)$ 是 $x$ 的必经点。如果 $idom(t)$ 不能用的话，在 $idom(t)$ 到 $t$ 的那一段都不能用，由于 $t$ 到 $x$ 的那段 $semi$ 不够小，所以绕不过。
      • 然后证明 $idom(x)$ 的深度不能更大。反证，如果深度更大，那么首先能到 $idom(t)$。此时利用 $semi(x) \rightarrow x$ 和 $idom(t) \rightarrow t$ 两个传送门，删除 $idom(t)$ 和 $x$ 之间的任意一个结点也无济于事。（注意到 $t$ 在 $semi(x)$ 和 $x$ 之间）

实现

  • 按照时间戳从大到小依次考虑每个结点
  • 利用带权并查集维护每个结点到其祖先的链上的 $semi$ 的最小值
  • 设当前要计算 $semi(x)$，考虑所有 $(u, x) \in E$：
    • 如果 $u>x$，那么 $semi(u)$ 已经完成计算，直接更新。
    • 如果 $u < x$，那么 $u$ 在并查集中是一个单独的结点，同样方式更新即可。
  • 接下来用 $x=semi(u) \rightarrow u$ 来更新 $u$ 的 $idom$，此时并查集中 $x$ 和 $fa(x)$ 还没有连边，所以直接查询并查集中 $u$ 的祖先链上的最小值
  • 最后把 $idom(x) \ne semi(x)$ 的结点的 $idom$ 按时间戳从小到大重新刷一遍
  • 代码详见模板库

参考资料