支配ツリーとLengauer-Tarjanアルゴリズム

ダミーディレクトリ

支配木の定義

を与える

はいくつかの性質

を与える.

支配ツリーを迅速に構築するLengauer-Tarjanアルゴリズムと具体的な実装

を紹介する
支配樹とは何か
次の条件を満たす有向図であるアクティブポイントの有向図.
支配木の上の点について、この点を切断すると、ソース点は必ずその息子に到達することができず、他の任意の点に到達することができる.
明らかに木です(もちろん後ろに証明があります)
支配木には実用的な用途がたくさんあるので、私は知りません.
いくつかの性質
1つの有向図について、ソース点がr r rであると仮定し、まずr r rからdfsツリーを構築する.
定義:1つの点u u uに対して、u u uを支配する点w wがwを満たすと̸ = u wot= u w̸=uかつw w w wがu u uを支配する他のu u uを含まない支配点に支配されると、w w wはu u u uの最近の支配点であり、i d o m(u)idom(u)idom(u)と記す.
通俗的に言えば、w w wはu u uに最も近い支配点であり、u u u uを適切に支配することができる.
Lemma 1:支配関係にループは存在しない.
Proof:a a a aがb bを支配すると、r r rからb b bは必ずa a a aを経由し、b b bがa a a a aを支配するとb b bに到達するにはa a a aを経由する必要があり、このときb b b bを経由せずに矛盾が生じる.
Lemma 2:ソース点を除いて,他の点には最近の支配点が1つしかない.
Proof:a a a aがb bを支配し、b b b bがc c cを支配すると、a a a a aがc c cを支配する.a a a aがc c c cを支配し、b b b bがc c cを支配すると、a a a a aがb b bまたはb b bを支配し、そうでなければ、a a a aを経ずにc c c cに到達する経路を見つけることができ、矛盾する.従って、u u uを支配するすべての点の集合は全系列関係を構成するので、上述した最近の支配点の定義を満たす点を常に見つけることができる.
Theorem 1:ある点とその最近の支配点を接続すると,この図は木を構成し,支配木の定義を満たす.
Proof:Lemma 1とLemma 2からこの図が木であることがわかります.u u uを切断すると,ソース点がu u uのいずれかの息子に到達することは不可能であることが容易に証明される.他の点については,支配木の定義とLemma 2から,この点がu uが切断されたかどうかの影響を受けないことが示唆された.
Theorem 1により,すべての点のi d o m idom idomが得られると,この図の支配木が容易に構築される.
では、i d o m idom idomはどうやって求めますか?
まず定義:1つの点u u uの半支配点w w wを存在経路w→urightarrow u w→uと定義し、w w wを除いて、この経路上の任意の点のdfsシーケンスがu u uに等しいdfsシーケンスよりも大きく、w w wはすべての条件を満たす点の中で最も小さいものであり、s d o m(u)sdom(u)sdom(u)sdom(u)sdom(u)と記す.
Lemma 3:任意の点uに対して̸ = r uot=r u̸=r,i d o m(u)idom(u)idom(u)は、dfsツリー上のu u uの祖先である.
Proof:先祖でなければ、必ずi d o m(u)idom(u)idom(u)idom(u)を通らない木の端だけを通る経路を見つけることができます.
Lemma 4:任意の点uに対して̸ = r uot=r u̸=r,s d o m(u)sdom(u)sdom(u)は、dfsツリー上のu u uの祖先である.
Proof:先祖でなければ、そのdfsシーケンスがu u uのdfsシーケンスより小さい場合、dfsの場合は必ずs d o m(u)sdom(u)sdom(u)sdom(u)を経てu u uに到達し、このときs d o m(u)sdom(u)sdom(u)はu u u uの先祖であり、矛盾を生じる.そうでなければ、dfsツリー上の点w w wがs d o m(u)sdom(u)sdom(u)である点wの祖先を見つけることができ、経路w→s d o m(u)→u wrightarrow sdom(u)rightarrow w→sdom(u)→uは定義を満たす経路であり、w wのdfsシーケンスはs d o m(u)sdom(u)sdom(u)sdom(u)のdfsシーケンスより小さく、矛盾を生じる.
Lemma 5:任意の点uについて̸ = r uot=r u̸=r,i d o m(u)idom(u)idom(u)は、dfsツリー上のs d o m(u)sdom(u)sdom(u)の祖先である.
Proof:先祖でなければ、r→s d o m(u)→u rrightarrow sdom(u)rightarrow u r→sdom(u)→uの経路を見つけることができ、ここでr→s d o m(u)rrightarrow sdom(u)r→sdom(u)はdfsツリーの端を通り、明らかにi d o m(u)idom(u)idom(u)を通らない.s d o m(u)→u sdom(u)rightarrow u sdom(u)→uこの経路上の任意の点のdfsシーケンスはu u u uよりも大きく,Lemma 3によりこの経路もi d o m(u)idom(u)idom(u)を経由しないため,i d o m(u)idom(u)idom(u)を迂回して矛盾を生じる経路が見つかった.
Lemma 6:任意の2点uについて̸ = r , v ̸ = r uot=r,vot=r u̸​=r,v̸=r、u u uがv vの祖先である場合、u u uはi d o m(v)idom(v)idom(v)idom(v)の祖先またはi d o m(v)idom(v)idom(v)idom(v)がi d o m(u)idom(u)idom(u)idom(u)idom(u)idom(u)idom(u)idom(u)idom(u)idom(u)idom(u)idom(u)idom(u)idom(u
Proof:そうでなければi d o m(u)idom(u)idom(u)はi d o m(v)idom(v)idom(v)の祖先であり、i d o m(v)idom(v)idom(v)はu u uの祖先であるため、i d o m(v)idom(v)idom(v)を迂回してu u u u uに到達し、さらにv v v vに到達する経路が存在し、矛盾を生じる.
Theorem 2:任意の点についてu̸ = r uot=r u̸=rであり、s d o m(u)→u sdom(u)righarrow u sdom(u)→uが木辺のみを通る経路上、s d o m(u)sdom(u)sdom(u)sdom(u)を含まない任意の点v v v v vがs d o m(u)sdom(u)sdom(u)がs d o m(v)sdom(v)sdom(v)sdom(v)sdom(v)の祖先または両者が等しい場合、i d o m(u)=s d o m(u)idom(u)=sdom(u)idom(u=sdom(u)idom(u)idom(u)=sdom(u)idom(u)id= sdom(u).
Proof:Lemma 5により、s d o m(u)sdom(u)sdom(u)がu u uを支配すると、i d o m(u)=s d o m(u)idom(u)=sdom(u)=sdom(u)idom(u)=sdom(u)となる.r→u rrightarrow u r→uのいずれかの経路に対して、dfsシーケンスの最大の点w wを取ってw w wを満たすのはs d o m(u)sdom(u)sdom(u)の祖先である.dfsシーケンスの最小の点x x xをとり,s d o m(u)sdom(u)sdom(u)がx x xの祖先であるか,あるいは両者が等しいことを満たす点が必ず存在することが容易に見出される.では、s d o m(x)sdom(x)sdom(x)はw w wであるが、w w wはs d o m(u)sdom(u)sdom(u)sdom(u)の祖先であるため、x=s d o m(u)x=sdom(u)x=sdom(u)であり、r→urightarrow u→uの経路は必ずs d o m(u)sdom(u)sdom(u)を通過するので、s d o m(u)sdom(u)sdom(u)sdom(u)がu u u uを支配する.
Theorem 3:任意の点についてu̸ = r uot=r u̸=r,s d o m(u)→u sdom(u)rightarrow u sdom(u)→uが木辺のみを通る経路上,s d o m(u)sdom(u)sdom(u)を含まない点では,s d o m(v)sdom(v)sdom(v)sdom(v)のdfsシーケンスが最小のv v v vに対して,s d o m(v)sdom(v)sdom(v)がs d o m(u)sdom(u)sdom(u)の祖先であることを満たすでは、i d o m(u)=i d o m(v)idom(u)=idom(v)idom(u)=idom(v)となる.
Proof:Lemma 5とLemma 6,i d o m(u)idom(u)idom(u)はi d o m(v)idom(v)idom(v)idom(v)idom(v)の祖先または両者が等しい.したがって,i d o m(v)idom(v)idom(v)がu u u uを支配することを証明すればよい.Theorem 2の証明と同様に、w w wをi d o m(v)idom(v)idom(v)の祖先、x x xをi d o m(v)idom(v)idom(v)idom(v)の子孫または両者が等しいと、s d o m(x)sdom(x)sdom(x)はw w w w wであり、またs d o m(v)sdom(v)sdom(v)sdom(v)sdom(v)が最大であるため、x x xがs d o m(u)sdom(u)sdom(u)の子孫であるはずがない.x x xがs d o m(u)sdom(u)sdom(u)の祖先であるか等しいが、i d o m(v)idom(v)idom(v)idom(v)の子孫である場合、i d o m(v)idom(v)idom(v)を迂回してv v vに到達する経路が見出される.したがってx x xはi d o m(v)idom(v)idom(v)である.全ての経路がi d o m(v)idom(v)idom(v)を通過するので、i d o m(v)idom(v)idom(v)はu u u uを支配する.
Theorem 2とTheorem 3によって、私たちは簡単にs d o m sdom sdomからi d o m idom idomを求めることができます.
Theorem 4:任意の点uについて̸ = r uot= r u̸=r,s d o m(u)sdom(u)sdom(u)は、以下の条件を満たす2つの条件のdfsシーケンスの最小のx x:1である.エッジx→u xrightarrow u x→uが存在し、x x xのdfsシーケンスはu u uのdfsシーケンスより小さい.2.x=s d o m(v)x=sdom(v)x=sdom(v)であり、v v vのdfsシーケンスはu uのdfsシーケンスよりも大きく、1つの点w w w w w w w wが1つのエッジw→u wrightarrow→uを満たし、v v v vがw w wの祖先であるか、または等しい.
Proof:明らかにx xごとにs d o m sdom sdomの要件を満たすパスが存在する.s d o m(u)sdom(u)sdom(u)sdom(u)の後の点dfsシーケンスは必ずu u u uに等しいので、s d o m(u)sdom(u)sdom(u)の後の点v v vをとると、s d o m(v)sdom(v)sdom(v)のdfsシーケンスは必ずs d o m(u)sdom(u)sdom(u)sdom(u)sdom(u)に等しく、v v v vは上述の条件に合致する.
Theorem 4からはs d o m sdom sdomを容易に求めることができる.
具体的な実装
dfsシーケンスの逆シーケンスで各ポイントを列挙し、1つのポイントを別のポイントの父親としてサポートするデータ構造があると仮定する.この点からルートまでのs d o m sdom sdom最小値をクエリーします.
現在の列挙点をu u uとし、u uの前駆x xを列挙できるとすると、s d o m(u)sdom(u)sdom(u)は、u uの前駆体のデータ構造上のs d o m sdom最小値の最小値である.
u u uの父親t t tについては、s d o m(w)=t sdom(w)=t sdom(w)=tであり、w w wはu uの子孫または両者が等しいw w wデータ構造上のs d o m sdomの最小値がTheorem 2およびTheorem 3で記述された最小値であり、w w wのi d o m idomを直接更新すればよい.
注意Theorem 3ではv v vのi d o m idomが更新されていない可能性があるので、i d o m(w)=v idom(w)=v idom(w)=vとし、その後i d o m(w)̸ = s d o m ( w ) idom(w)ot=sdom(w) idom(w)̸=sdom(w)は、i d o m(i d o m(w))idom(idom(w))idom(idom(w))に更新される.
データ構造は帯域重みを用いて集合を調べることができ,時間複雑度O(n log⁡n)O(nlog n)O(nlogn)
コード#コード#

//dfn[i] i dfs ，idfn[i] dfs  i  ，het[i] i     ，bkt[i]   sdom i  
//eval(i)              sdom dfs      
int getidom()
{
  for(int i=cnt; i>1; --i)
    {
      int u=idfn[i];
      for(int v:het[u])
        {
          if(!dfn[v])
            {
              continue;
            }
          int w=eval(v);
          if(dfn[sdom[w]]<dfn[sdom[u]])
            {
              sdom[u]=sdom[w];
            }
        }
      bkt[sdom[u]].push_back(u);
      int t=fa[u];
      dsu::fa[u]=t;
      for(int v:bkt[t])
        {
          int w=eval(v);
          idom[v]=(sdom[w]==sdom[v])?t:w;
        }
      bkt[t].clear();
    }
  for(int i=2; i<=cnt; ++i)
    {
      int u=idfn[i];
      idom[u]=(idom[u]==sdom[u])?(idom[u]):(idom[idom[u]]);
    }
  return 0;
}