算法 - 支配树 (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\) 的最小值
  • 设当前要计算 \(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
  • 《支配树》河南省实验中学 王梦迪