算法 - 支配树 (Lengauer Tarjan)

Posted on 2018-10-22 Edited on 2019-03-06 In Algorithms 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\) 按时间戳从小到大重新刷一遍
代码详见模板库