算法 - 支配树 (Lengauer Tarjan)
对于有向图 $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(x)=semi(t)$,那么 $idom(x) = semi(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$ 按时间戳从小到大重新刷一遍
- 代码详见模板库
参考资料
- 《图连通性若干拓展问题探讨》北京大学 李煜东
- https://www.cnblogs.com/fenghaoran/p/dominator_tree.html
- https://blog.csdn.net/a710128/article/details/49913553
- 《支配树》河南省实验中学 王梦迪