算法 - 支配树 (Lengauer Tarjan)

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

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

半必经点

考虑 G 的搜索树，定义 semi(x) 是 {u|存在dfn[p_i] > dfn[x] 使得 u, p₁, p₂, …, p_k, x 是一条路径} 中 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) ∈ E
  • u < x，也就是树边或者前向边，此时有 semi(x) ≤ u，也就是路径 u → x。
  • u > x，也就是后向边或者横叉边，对于所有满足 v > x 的 u 的祖先 v，有 semi(x) ≤ semi(v)，也就是路径 semi(v) → v → u → x。
  • 这样就考虑了 semi(x) → x 的最后一条边的所有可能。

必经点

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

性质

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

实现

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

参考资料

• 《图连通性若干拓展问题探讨》北京大学 李煜东
• https://www.cnblogs.com/fenghaoran/p/dominator_tree.html
• https://blog.csdn.net/a710128/article/details/49913553
• 《支配树》河南省实验中学 王梦迪