支配树速成记录

支配树和其他图论知识没什么关系,学习曲线极大,我在省选前根本静不下心来好好看;现在也没这个耐心,只是简单地看了看概念,从结论自己脑补出证明,参考了几篇博客,止步于此。当然,没有理解透的东西一定是记不牢的,所以为了在以后复习的时候能够快速地恢复对支配树的记忆,我把现在能理解的东西先记录下来吧。

想了解严格的证明和更多拓展知识,请见L-T原论文。本着“速成”的目的,我没有仔细研究这篇论文,所以在下面没有作严格的证明,也不保证正确性,大家就看着玩玩吧。如果你想把我批判一番,欢迎联系。

正文开始。

支配点

俗话说,条条大路通罗马(Rome)。在一个单源(源点设为rr)有向图中,如果删掉点uu后,从罗马出发就到不了vv了,那么称“uu支配vv”。如果uu支配vv,称uuvv的“支配点”,或者像在李煜东的PPT里面叫“必经点”。除了rr以外,每个点都至少有两个支配点,一个是源点,一个是自己。

说实话,我觉得必经点是更准确的叫法,支配点应该是原论文中Dominator的翻译。但是“必经树”这个叫法听起来挺奇怪的,所以我还是配套地叫支配点吧。


约定

在继续讲述之前,我们先对一些符号和术语进行约定。

  • 我们讨论的这张图的点集为VV,边集为EE
  • 我们已经对这种图从rr开始DFS过一遍了。除非特殊说明,我们只讨论被DFS过(即从rr出发能到达)且不为源点的点。
  • 两个节点uuvv的比较使用的是他们的dfn,即到达他们的时间戳。
  • uvu\to v表示从uuvv有合法路径,或一条从uuvv的合法路径,或从uuvv的合法路径集合。我们都不是编译器,应该都有比较强大的上下文引擎,都知道我是什么意思,所以我就统一记成这样了。
  • u˙vu\dot\to v是和上面类似的定义,但是这里的从uuvv只能沿着DFS外向树走。内在要求:uuvv的DFS祖先。
  • 无特殊说明,路径起点可以等于终点。

为什么是树

  1. 支配是具有传递性的。若uu支配vvvv支配ww,那么uu同样支配ww
  2. 显然对于点ww的支配点集合中的每一个元素uuu˙wu\dot\to w
  3. 在点ww的支配点集合中,元素之间的关系只能是支配或者被支配。如果集合中的元素uuvv没什么大关系,就会存在r˙u˙wr\dot\to u\dot\to wr˙v˙wr\dot\to v\dot\to w两条路径到达ww,与uuvv的定义矛盾。
  4. 选取点ww的支配点集合中最大的那个元素,也就是在DFS树上距离最近的一个支配点,作为最近支配点(Immediate Dominator),记为idom(w)idom(w)。每个点只有一个最近支配点,从idom(w)idom(w)ww连边,可以得到一颗以rr为根的树,这棵树就是支配树。

若无特殊说明,从这里往下讨论的支配点指的都是最近支配点。


半支配点

直接求支配点不太方便,我们引入一些新的东西来辅助一下。

uv={(u,w1,...,wn,v)i,wi>v}u\leadsto v=\left\{(u,w_ 1,...,w_ n,v)|\forall i,w_ i>v\right\}

我规定这个记号也可以表示和上面的\to一样多的意思。

定义半支配(必经)点(Semi-Dominator):

sdom(w)=min{uuw}sdom(w)=min\left\{u|u\leadsto w\right\}

我对半支配点的理解,就是从rr换一条路[1]ww,取uu为这条路径上最后一个小于ww的点,sdom(w)sdom(w)选取的是所有路径中最小的uu,这是用贪心的思路来找支配点。当然这个算法知道这样做是错误的,因为半支配点的换路方法是仅限于以ww为换路终点的;如果我们把换路终点设在ww前面,换完路之后再继续沿着DFSDFS树走,这样就可能绕过半支配点,所以半支配点不一定是支配点,但是有潜力支配ww

怎么求sdomsdom

  1. sdom(w)wsdom(w)\leadsto w没有中间节点(n=0n=0),即{u(u,w)E,u<w}\left\{u|(u,w)\in E,u<w\right\}中的节点都可以拿来更新sdom(w)sdom(w)。比如说,DFS树上的fa(w)fa(w)就可以。
  2. sdom(w)wsdom(w)\leadsto w存在中间节点(n>0n>0)的情况下,如果u>w,u˙v,(v,w)Eu>w,u\dot\to v,(v,w)\in E,那么sdom(u)wsdom(u)\leadsto w,且uusdom(u)wsdom(u)\leadsto w的一个中间节点,vv是中间节点的最后一个。这样一来,又可以用sdom(u)sdom(u)来更新sdom(w)sdom(w)了。

还有没有别的情况?n=0n=0的情况1的的确确已经覆盖完了;在n>0n>0的情况2中我们枚举了sdom(w)wsdom(w)\leadsto w的中间节点里的最后一段严格上升的区间(只能是顺着DFSDFS树走)。应该说,囊括完全了。

开始设计算法吧。

  1. 为了实现情况2,我们需要一个能够查询u>wu>wu˙v,(v,w)Eu\dot\to v,(v,w)\in E的数据结构。数据结构哪里是想要就有的?注意到uuvv都是大于ww的,也就是说从情况2更新的sdom(w)sdom(w)只和大于ww的节点有关系。所以我们按照dfn倒着计算sdom(w)sdom(w)
  2. 要找到满足条件的uu不太好找……uu要满足什么条件?有三:u>w,u˙v,(v,w)Eu>w,u\dot\to v,(v,w)\in E。我们需要枚举vv,顺着vv的DFS父亲链往上找最小的sdom(u)sdom(u),往上的同时还要保证u>wu>w。有没有感觉很LCA?而且,specifically,Tarjan版离线LCA!Tarjan的思路在他不同的算法中体现出了统一性:我们采用并查集作为这个“数据结构”。
  3. 类似Tarjan求LCA算法,初始化并查集的fafa值为自己,在__处理完ww的时候就顺手把自己DFS孩子的并查集父亲设为自己__。这样我们顺着并查集的父亲链往上找的时候,能找到所有大于当前点的点。
  4. 要顺便__维护一下到并查集根的路径上sdomsdom最小值__。因为要维护到并查集根的信息,路径压缩写的了,但是按秩合并就不太方便了,这样的话每次操作均摊复杂度会降为O(logn)O(\log n)
  5. 对于情况1,因为比ww小的节点还没有开始处理,所以他们的并查集的根和到根的sdomsdom最小值都是自己,所以__情况1直接当作情况2处理__后还是满足上面的做法的。这一步实在是太优美了,我不能赞叹更多。

质的飞跃

为了显得有理有据,我还要规范一些说法。

  • P[uv]P[u\to v]表示路径PP中属于uvu\to v的子路径的集合。
  • uu是从rr出发的路径PP的“换路终点”当且仅当uPu\in Puu是满足P[uw]=u˙wP[u\to w]=u\dot\to w的最小的点。如果u=ru=r,我们认为这个路径PP没有换路。
  • 路径P=rwP=r\to w的换路终点uu对应的换路起点我们认为是max{vr˙wv<u}max\left\{v\in r\dot\to w|v<u\right\}。没有换路的路径没有换路起点。

根据这些定义,容易发现(sdom(w),w)(sdom(w),w)就是一对有效的换路起点和换路终点。

继续往下之前,请先思考一个命题:r˙idom(w)˙sdom(w)˙wr\dot\to idom(w)\dot\to sdom(w)\dot\to w(原论文引理的三合一)。这使得我们考虑的绝大多数问题都在r˙wr\dot\to w这条链上。

对于一个点wwsdom(w)sdom(w)不一定等于idom(w)idom(w)。这是为什么呢?应该不难发现,sdom(w)sdom(w)规定的换路终点必须是ww,但实际上,我们可以选择比ww小的换路终点来实现换路,比如说rsdom(u)u˙w(u<w)r\to sdom(u)\leadsto u\dot\to w(u<w)

那这个时候就有点思路了。我们如果要确定sdom(w)sdom(w)就是idom(w)idom(w),需要保证无论我们如何选取换路终点都还是必须要经过sdom(w)sdom(w)。设我们现在换了一条路,设该路径换路终点为uu。根据定义有ur˙wu\in r\dot\to w

  1. usdom(w)u\leq sdom(w),根据上面换路终点的定义,我们必须继续沿着DFS树走下去,而易得u˙sdom(w)˙wu\dot\to sdom(w)\dot\to w,经过了sdom(w)sdom(w)
  2. sdom(w)<uwsdom(w)<u\leq w
    • sdom(u)sdom(w)sdom(u)\geq sdom(w)恒成立,由sdomsdom定义知道uu对应的换路起点vsdom(u)v\geq sdom(u),推出vsdom(w)v\geq sdom(w)。拿定义说话,换路起点终点、sdom(w)sdom(w)都在r˙wr\dot\to w上,r˙wr\dot\to w严格递增,而换路起点终点又跨不过sdom(w)sdom(w),不就是必经sdom(w)sdom(w)的意思吗?
      • 小思考1:有没有可能在vv之前找一个换路终点继续换路从而跨过sdom(w)sdom(w)呢?
    • u,sdom(u)<sdom(w)\exists u,sdom(u)<sdom(w),假设sdom(u)sdom(u)最小的uuuu',那么r˙sdom(u)˙sdom(u)˙u˙wr\dot\to sdom(u')\dot\to sdom(u)\dot\to u\dot\to w,发现不存在一种uu和它对应的起点跨过sdom(u)sdom(u')。那sdom(u)sdom(u')就是idom(w)idom(w)了吗?不一定,在sdom(w)sdom(w)之前还可能有换路终点呢。我们都没怎么考虑sdom(w)sdom(w)之前的情况,那怎么办呢?实际上,我们也不需要考虑,我们用DP的思想,把问题归结成子问题即可。我们让sdom(w)sdom(w)之前的情况让uu'去handle,在uu'之前一刀劈开能不能换路界限的又是谁?非idom(u)idom(u')者莫属也(其实还有idom(u)idom(u')的支配树祖先)。$$r\dot\to idom(u’)\dot\to sdom(u’)\dot\to sdom(w)\dot\to u’\dot\to w$$观察:如果换路终点在sdom(w)˙wsdom(w)\dot\to w上,根据我们uu'的选择,换路起点是跨不过sdom(u)sdom(u')的;换路终点在idom(u)˙uidom(u')\dot\to u'上,又被idom(u)idom(u')的性质保证换路起点不能跨过idom(u)idom(u')。所以idom(u)idom(u')支配ww
      • 小思考2:idom(u)idom(u')是不是ww最近的支配点?
  3. u>wu>w,别搞笑了,看定义。

综上所述,我们最终得出了最终能够帮助我们求出idomidom的式子:

uusdom(w)˙wsdom(w)\dot\to wusdom(w)u\neq sdom(w))上sdom(u)sdom(u)最小的点,

idom(w)={sdom(u)(sdom(u)=sdom(w))idom(u)(sdom(u)<sdom(w))idom(w)=\left\{ \begin{aligned} &sdom(u)&(sdom(u)=sdom(w))&\\ &idom(u)&(sdom(u)<sdom(w))& \end{aligned} \right.

这一段理解十分辛苦,但是量变积累足矣,我们可以求支配树了。

Lengauer-Tarjan算法

设一个点ww到它并查集根的sdomsdom最小值为eval(w)eval(w)

  1. 老老实实DFS一遍得到DFS序。
  2. 因为半支配点的求解和支配点初次判断都需要维护evaleval操作,所以按dfn倒序处理出sdomsdom数组。
    1. 半支配点部分:在退出一个点ww的时候把ww的所有DFS儿子的并查集父亲设为自己;在处理一个点ww的时候遍历入点vv,用eval(v)eval(v)来更新sdom(w)sdom(w)
    2. 支配点部分:给每个点开一个bucket(可用链表实现),在退出一个点ww的时候把自己加入sdom(w)sdom(w)的全家桶;在处理一个点ww的时候处理在自己桶里的点vv,如果sdom(v)=sdom(eval(v))sdom(v)=sdom(eval(v)),根据上面的最终公式令idom(v)=sdom(v)idom(v)=sdom(v);否则,在实现上我们可以令idom(v)=eval(v)idom(v)=eval(v),留到第三步处理。
  3. 再按DFN序正着跑一遍,处理完不正确的idomidom。如果idom(w)=sdom(eval)idom(w)=sdom(eval)则已经正确;如果idom(w)!=sdom(w)idom(w)!=sdom(w)说明是最终公式的情况二,如果用第二步里提到的实现方法,只要令idom(w)=idom(idom(w))idom(w)=idom(idom(w))即可。
  4. 现在已经得到除了源点以外所有点的支配树父亲,要在搞出字面意义上的树的话,只需连上所有父亲到儿子的边。结束。

后记

我没有翻译原论文,导致学习和记录支配树一点都不“速成”,花了我两天的上机时间和走路+吃饭的思考时间,才写出这么一篇短浅的理解来。当然,这么做还是有很多思想上的收获的,自己对这些概念的理解得到了加深,形成了一套自己的思想体系,忘得应该不会那么快了。

几个不足的地方:

  1. 我还没有实现出来。
  2. 在这种时候花费了这么多时间,别人都刷了几十道题了。
  3. 标题起的完全不对,从实际过程来看,应该叫“支配树思考笔记”;从SEO的角度来看,“支配”和“换路”是最高频的词,应该叫”支配树换路记”。
  4. 修改太多,落笔前没有完全想好细节,一改再改。这可能也是我作文写不好的原因之一吧。

  1. 换路、换路终点、换路起点的定义会在下面的章节中提到。

avatar
Kerry Su