Dominator Tree

问题引入

题目要求解决的模型: 给定有向图G(可能有环)和图中的一个点r,对于G中的任意一个点x,求从r到x的路径上(可能有很多条)必须经过的点集。

  • Flow Graph:若有向图G中存在一点r,从r出发可到达G中所有的点,则称G是Flow Graph,记为(G,r)。
  • 必经点(dom):若在(G,r)中从r到y的路径一定经过点x,则称x是从r到达y的必经点,记为x dom y。 从r出发到达y的所有必经点构成的集合记为dom(y),即dom(y)={x | x dom y}。
  • 最近必经点(idom): 节点y的必经点集合dom(y)中dfn值最大的点x是距离y最近的必经点,称为y的最近必经点。最近必经点是唯一的,因此可以记x=idom(y)。

于是可以按下面\(O(V^2)\)暴力求解

  • \(pre(y)=\{x|(x,y)\in E\}\) y的前驱节点集合
  • \(suc(x)=\{y|(x,y)\in E\}\) x的后继节点集合
  • \(dom(r)=\{r\}\)
  • \(dom(y)=\cap _{x\in pre(y)} dom(x) \cup \{y\}\)
  • \(idom(x)=id[Max\{dfn[y]|y\in dom(x)\}]\)

Dominator Tree

设有向图G=(V,E),(G,r)是一个Flow Graph,则称(G,r)的子图\(D=(V, \{ (idom(i),i) | i\in V , i\neq r \}, r)\)为(G,r)的一棵Dominator Tree。

(G,r)的Dominator Tree是一棵有向有根树,从r出发可以到达G中的所有点,并且树上的每条边(u,v)都满足:u=idom(v),即父节点是子节点的最近必经点。

  • x=idom(y),当且仅当有向边(x,y)是Dominator Tree中的一条树枝边。
  • x dom y,当且仅当在Dominator Tree中存在一条从x到y的路径。
  • x的必经点集合dom(x)是Dominator Tree上x的所有祖先以及x自身。

半必经点

半必经点(semi) 在搜索树T上点y的祖先中,经过时间戳比y大的节点可以到达y的深度最小的祖先x,称为y的半必经点。关于半必经点有如下性质:

  • 半必经点也是唯一的,因此可以记x=semi(y)。
  • 一个点的半必经点必定是它在dfs树上的祖先,dfn[semi[x]]<dfn[x]
  • 半必经点不一定是x的必经点。

如何求半必经点:对于G中一点y,考虑所有\(x\in pre(y)\),设\(temp=INF\)。

  • 若dfn[x]<dfn[y],则(x,y)为树枝边或前向边,此时\(temp=min(temp,dfn[x])\)
  • 若dfn[x]>dfn[y],则(x,y)为横叉边或后向边,此时任意x在T中的祖先z,满足dfn[z]>dfn[y]时,\(temp=min(temp,dfn[semi[z]])\)
  • \(semi[y]=id[temp]\)

必经点

对于G中的一点x,考虑搜索树T中semi(x)到x的路径上除端点之外的点构成的集合path

设\(y=id[min\{dfn[semi(z)]|z\in path\}]\),即path中半必经节点的时间戳最小的节点。

  • \(semi(x)=semi(y)\)时,\(idom(x)=semi(x)\)
  • \(semi(x)\neq semi(y)\)时,\(idom(x)=idom(y)\)

题目

1.hdu 4694 Important Sisters

给一个有向图,输出每个点的必经点集合里的点的编号和,源点是n

2.2017-2018 Petrozavodsk Winter Training Camp, Saratov SU Contest L

无向图,边有边权,起点为1号点,记起点到点k的最短路为dk,询问如果增大输入中第i条边的边权,最短路会受到影响的点有多少个。

做法很自然,在最短路构成的DAG上求支配树,询问的就是支配树子树大小了。这里把边新建点,方便处理。