當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

【学习笔记】DAG / 一般有向图的支配树 / 灭绝树

發(fā)布時間：2023/12/3 编程问答 26 豆豆

生活随笔收集整理的這篇文章主要介紹了【学习笔记】DAG / 一般有向图的支配树 / 灭绝树小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

定義與聲明

一個有向圖 $G$ 。給定一個起點(diǎn) $s$ ，假設(shè) $s$ 能到達(dá)所有點(diǎn)。

若去掉某個點(diǎn) $i$ 后， $s$ 無法到達(dá) $j$ ，則稱 $i$ 為 $j$ 的支配點(diǎn)。

顯然支配點(diǎn)存在傳遞關(guān)系。

以 $s$ 為根，使得對于任意節(jié)點(diǎn) $i$ ，其樹上祖先均為 $i$ 的支配點(diǎn)，這樣的樹稱之為支配樹。（有的人叫做滅絕樹）

任一有向圖都存在支配樹，前提是滿足 $s$ 能到達(dá)所有點(diǎn)。

支配樹不一定是圖 $G$ 的樹形圖，即樹上有些邊不存在于圖 $G$ 中。

$dfs\text{dfs}$ 樹。

對圖 $G$ 建 $dfs\text{dfs}$ 樹。每個點(diǎn)有一個 $dfn\text{dfn}$ 序，即 $dfs\text{dfs}$ 的時間戳。

$dfs\text{dfs}$ 樹中的邊稱為樹邊，除此之外的原圖中的邊稱為非樹邊。

非樹邊又分為前向邊，返祖邊，橫叉邊。前向邊是 $dfn\text{dfn}$ 序小的連向大的，返祖邊和橫叉邊則相反。

最近支配點(diǎn) $idom\text{idom}$ 。

點(diǎn) $i$ 的支配點(diǎn)中 $dfn\text{dfn}$ 序最大的點(diǎn)，即支配樹上 $i$ 的父親。

注意：支配樹上的父親不一定就是 $dfs\text{dfs}$ 樹上的父親。

顯然，除 $s$ 以外的所有點(diǎn)均有唯一的 $idom\text{idom}$ 。

半支配點(diǎn) $sdom\text{sdom}$ 。

點(diǎn) $v$ 的半支配點(diǎn) $u$ 是滿足『 $G$ 中存在一條從點(diǎn) $u$ 到點(diǎn) $v$ 的路徑，且路徑上經(jīng)過點(diǎn)的 $dfn>dfn[v]\text{dfn}>\text{dfn}[v]$ （不包含 $u, v$ ）』的 $dfn\text{dfn}$ 最小的點(diǎn)。

即 $u$ 只走非樹邊能到達(dá) $v$ 的 $dfn\text{dfn}$ 最小的 $u$ 。

特別的，如果 $u$ 有一條邊直接連向 $v$ ，則也是 $sdom(v)\text{sdom}(v)$ 的候選點(diǎn)，這相當(dāng)于路徑上沒有其他點(diǎn)。

$u→v:uu\rightarrow v:u$ 存在一條直接連向 $v$ 的邊。

$u?^v:u\hat\leadsto v:$ 存在一條由樹邊組成的 $u$ 到 $v$ 的路徑，且 $u≠vu\ne v$ 。

$u?¨v:u\ddot\leadsto v:$ 存在一條由樹邊組成的 $u$ 到 $v$ 的路徑，允許 $u = v$ 。

注意：下面引理和定理的樹均指 $dfs\text{dfs}$ 樹，而非支配樹。樹邊/非樹邊也是在 $dfs\text{dfs}$ 樹的基礎(chǔ)上定義的。

引理與定理

引理Ⅰ： $?i≠s\forall_{i\ne s}$ 有 $idom(i)?^i\text{idom}(i)\hat\leadsto i$ 。 $idom(i)\text{idom}(i)$ 一定是 $dfs\text{dfs}$ 樹上 $i$ 的某個祖先點(diǎn)。

顯然。如果不是，那么去掉 $idom(i)\text{idom(i)}$ 后， $s$ 可以通過走樹邊訪問到 $i$ 。這就不滿足『支配』的定義了。
引理Ⅱ： $?i≠s\forall_{i\ne s}$ 有 $sdom(i)?^i\text{sdom}(i)\hat\leadsto i$ 。 $sdom(i)\text{sdom(i)}$ 一定是 $dfs\text{dfs}$ 樹上 $i$ 的某個祖先點(diǎn)。

假設(shè) $sdom(i)\text{sdom}(i)$ 不是 $i$ 的祖先，那么我們可以從 $sdom(i)\text{sdom}(i)$ 開始沿著樹邊往上走，直到走到 $i$ 的某個祖先點(diǎn) $x$ 上。

這期間肯定不會經(jīng)過除 $x$ 外的任何一個 $i$ 的祖先點(diǎn)。

顯然 $x$ 更符合 $sdom\text{sdom}$ 的條件。
引理Ⅲ： $?i≠s\forall_{i\ne s}$ 有 $idom(i)?¨sdom(i)\text{idom}(i)\ddot\leadsto\text{sdom}(i)$ 。 $idom(i)\text{idom}(i)$ 要么是 $sdom(i)\text{sdom}(i)$ ，要么是 $sdom(i)\text{sdom}(i)$ 的祖先。

通過前面的引理，我們知道 $idom(i),sdom(i)\text{idom}(i),\text{sdom}(i)$ 一定都在支配樹中 $i$ 到根的路徑上，即是 $i$ 的某個祖先點(diǎn)。

所以引理如果不成立，我們就可以從 $s$ 直接走到 $sdom(i)\text{sdom(i)}$ 然后走到 $i$ ，且沒有經(jīng)過 $idom(i)\text{idom}(i)$ 。

這顯然不符合 $idom(i)\text{idom}(i)$ 的定義。所以引理一定成立。
引理Ⅳ： $?u?¨v\forall\ u\ddot\leadsto v$ ，有 $u?¨idom(v)u\ddot\leadsto \text{idom}(v)$ 或 $idom(v)?¨idom(u)\text{idom}(v)\ddot\leadsto\text{idom}(u)$ 。

$u,v,idom(u),idom(v)u,v,\text{idom}(u),\text{idom}(v)$ 都在根到某個葉子節(jié)點(diǎn)的路徑上。

引理也就是說這兩條 $idom(x)\text{idom}(x)$ 到 $x$ 的路徑完全不交或包含。

分情況討論：
- $dfn[u]≤dfn[idom(v)]\text{dfn}[u]\le \text{dfn}[\text{idom}(v)]$ 。
  
  此時有 $u?¨idom(v)?¨vu\ddot\leadsto \text{idom(v)}\ddot\leadsto v$ 。完全不交。
- $dfn[u]>dfn[idom(v)]\text{dfn}[u]>\text{dfn}[\text{idom}(v)]$ 。
  
  此時有 $idom(v)?¨u\text{idom}(v)\ddot\leadsto u$ 。
  
  然后要么有 $idom(u)?¨idom(v)\text{idom}(u)\ddot\leadsto \text{idom}(v)$ ，要么有 $idom(v)?¨idom(u)\text{idom}(v)\ddot\leadsto \text{idom}(u)$ 。
  
  如果 $idom(u)?¨idom(v)\text{idom}(u)\ddot\leadsto \text{idom}(v)$ ，那么去掉 $idom(v)\text{idom}(v)$ ， $idom(u)\text{idom}(u)$ 一定還能到達(dá) $u$ ，否則 $idom(u)\text{idom(u)}$ 就不是 $u$ 的支配點(diǎn)，而 $idom(v)\text{idom}(v)$ 才是了。
  
  所以也一定能到達(dá) $v$ 。這樣又不符合 $idom(v)\text{idom}(v)$ 的定義了。矛盾。
  
  所以有 $idom(v)?¨idom(u)\text{idom}(v)\ddot\leadsto \text{idom}(u)$ 。包含。
定理Ⅰ： $?u≠s\forall\ u\ne s$ ，如果 $sdom(u)?^v?¨u∧dfn[sdom(v)]≥dfn[sdom(u)]\text{sdom}(u)\hat\leadsto v\ddot\leadsto u\ \wedge\ \text{dfn}[\text{sdom}(v)]\ge\text{dfn}[\text{sdom}(u)]$ ，則有 $idom(u)=sdom(u)\text{idom}(u)=\text{sdom}(u)$ 。

前提條件意思就是：

對于所有滿足 $sdom(u)\text{sdom}(u)$ 是 $v$ 祖先， $v$ 是 $u$ 祖先（可以相等）的 $v$ ，均滿足 $sdom(u)\text{sdom(u)}$ 到 $u$ 的路徑完全包含 $sdom(v)\text{sdom}(v)$ 到 $v$ 的路徑。
定理Ⅱ： $?u≠s\forall\ u\ne s$ ，如果 $sdom(u)?^v?¨u\text{sdom}(u)\hat\leadsto v\ddot\leadsto u$ ，假設(shè) $v$ 是 $dfn[sdom(v)]\text{dfn}[\text{sdom(v)}]$ 最小的點(diǎn)，

且如果 $dfn[sdom(v)]<dfn[sdom(u)]\text{dfn}[\text{sdom}(v)]<\text{dfn}[\text{sdom}(u)]$ ，則有 $idom(u)=idom(v)\text{idom}(u)=\text{idom(v)}$ 。
- 結(jié)合以上兩個定理有，推論Ⅰ： $?u≠s\forall\ u\ne s$ ，令 $u$ 為所有滿足 $sdom(v)?^u?¨v\text{sdom}(v)\hat\leadsto u\ddot\leadsto v$ 的 $u$ 中 $dfn[sdom(u)]\text{dfn}[\text{sdom}(u)]$ 最小的點(diǎn)。
  
  有 $idom(v)={sdom(v)sdom(u)=sdom(v)idom(u)sdom(u)<sdom(v)\text{idom}(v)=\begin{cases}\text{sdom}(v)&\text{sdom}(u)=\text{sdom}(v)\\\text{idom}(u)&\text{sdom}(u)<\text{sdom}(v)\end{cases}$ 。
定理Ⅲ： $?u≠s\forall\ u\ne s$ ，有 $sdom(u)=min?{v∣(v,u)∈E,v<u}\text{sdom}(u)=\min\Big\{v\mid (v,u)\in E\ ,\ v<u\Big\}$

$sdom(u)\text{sdom}(u)$ 的候選點(diǎn)只用考慮兩類：
- 由樹邊或者前向邊直接連過來的點(diǎn)。
- $dfn\text{dfn}$ 更大的且與 $u$ 有邊相連的點(diǎn)及其祖先的 $sdom\text{sdom}$ 。這又可以分為兩類：
  - $dfn[v]>dfn[u],?(v,u)∈E\text{dfn}[v]>\text{dfn}[u],\exist(v,u)\in E$ ，則 $sdom(v)\text{sdom}(v)$ 一定是 $sdom(u)\text{sdom}(u)$ 的一個候選點(diǎn)。
  - 滿足 $dfn[v]>dfn[u],?(v,u)∈E\text{dfn}[v]>\text{dfn}[u],\exist(v,u)\in E$ 的 $v$ 的部分祖先，且這些祖先的 $dfn>dfn[u]\text{dfn}>\text{dfn}[u]$ ，則這些祖先的 $sdom\text{sdom}$ 也是候選點(diǎn)。

定理Ⅰ，Ⅱ?qū)嵲诓粫C明，感性理解好了，直接開始擺爛

大本鐘下寄快遞，上面開擺下面寄

算法步驟

建立支配樹的算法步驟：

如果對于一棵樹，樹根為 $s$ ，那么這棵樹本身就是一棵支配樹。
如果是一個 $DAG\text{DAG}$ ，則可以拓?fù)渑判颉Ｈ缓笠来未_定每個點(diǎn)的 $idom\text{idom}$ 。

設(shè)當(dāng)前點(diǎn)為 $i$ ，有 $j→ij\rightarrow i$ ，則所有 $j$ 在支配樹中的 $LCA\text{LCA}$ 就是 $idom(i)\text{idom}(i)$ 。

拓?fù)?span id="ze8trgl8bvbq" class="katex--inline"> $+$ 倍增時間大概 $O((n+m)log?n)O((n+m)\log n)$ 。
如果是一般圖問題，則可以先求出每個點(diǎn)的 $sdom\text{sdom}$ ，然后對所有點(diǎn)，連邊 $(sdom(i),i)(\text{sdom}(i),i)$ ，去掉非樹邊，就形成了 $DAG\text{DAG}$ 。支配關(guān)系與原圖一致。

代碼實(shí)現(xiàn)

$DAG\text{DAG}$ 模板題：ZJOI2012 災(zāi)難

代碼實(shí)現(xiàn)：

#include <bits/stdc++.h> using namespace std; #define maxn 66000 int dep[maxn], deg[maxn], f[maxn][20], siz[maxn]; vector < int > pre[maxn], G[maxn], rG[maxn]; queue < int > q; int n;void dfs( int u, int fa ) {siz[u] = 1;for( int v : rG[u] ) if( v ^ fa ) dfs( v, u ), siz[u] += siz[v]; }int LCA( int u, int v ) {if( dep[u] < dep[v] ) swap( u, v );for( int i = 19;~ i;i -- ) if( dep[f[u][i]] >= dep[v] ) u = f[u][i];if( u == v ) return u;for( int i = 19;~ i;i -- ) if( f[u][i] ^ f[v][i] ) u = f[u][i], v = f[v][i];return f[u][0]; }int main() {scanf( "%d", &n );for( int i = 1, x;i <= n;i ++ ) {while( ~ scanf( "%d", &x ) and x ) //G[x]:x有dfs樹路徑到的點(diǎn)的集合G[x].push_back( i ), deg[i] ++;}int root = 0; //新建大起點(diǎn) 即使其變成有根樹//pre[i]:i的前驅(qū)集合即從根開始有dfs樹路徑到i的點(diǎn)for( int i = 0;i <= n;i ++ )if( ! deg[i] ) pre[i].push_back( root ), q.push( i );while( ! q.empty() ) {int u = q.front(); q.pop();int lca = pre[u][0];for( int x : pre[u] ) lca = LCA( lca, x );dep[u] = dep[lca] + 1;f[u][0] = lca;//建立支配樹上的關(guān)系for( int i = 1;i < 20;i ++ )f[u][i] = f[f[u][i - 1]][i - 1];rG[lca].push_back( u );for( int v : G[u] ) {pre[v].push_back( u );//u是v的前驅(qū)之一if( ! -- deg[v] ) q.push( v );}}dfs( root, -1 );for( int i = 1;i <= n;i ++ ) printf( "%d\n", siz[i] - 1 );return 0; }

一般有向圖模板題：luogu-P5180 【模板】支配樹

代碼實(shí)現(xiàn)：

#include <queue> #include <cstdio> #include <vector> #include <iostream> using namespace std; #define maxn 200005 struct node {vector < int > g[maxn];void AddEdge( int u, int v ) {g[u].push_back( v );} }G, rG, Dfs, rDfs, dominate;//原圖反圖 dfs樹反dfs樹支配樹 queue < int > q; int n, m, cnt; int id[maxn], dfn[maxn], fa[maxn], anc[maxn], min_anc[maxn], sdom[maxn], d[maxn], dep[maxn], ans[maxn]; int f[maxn][20]; /* Semi-domination半支配表示v點(diǎn)的所有半支配點(diǎn)的最小的那個半支配點(diǎn)：存在從一個點(diǎn)u到v的路徑中(不包括u，v)，所有dfs樹的點(diǎn)的dfn都大于v的dfn 如果u是v在dfs樹上的父節(jié)點(diǎn)，那么u也是v的半支配點(diǎn) */void dfs( int u ) {//尋找dfs樹id[dfn[u] = ++ cnt] = u; //打時間戳for( int i = 0;i < G.g[u].size();i ++ ) {int v = G.g[u][i];if( dfn[v] ) continue; else;fa[v] = u;Dfs.AddEdge( u, v );dfs( v );} }int find( int x ) {if( x == anc[x] ) return x;int father = anc[x];anc[x] = find( anc[x] );if( dfn[sdom[min_anc[x]]] > dfn[sdom[min_anc[father]]] )min_anc[x] = min_anc[father];// min_anc表示x到sdom[x]路徑上dfn[sdom]值最小的點(diǎn)return anc[x]; }void build_dfs() {//建立與原圖等價的DAGfor( int i = 1;i <= n;i ++ )anc[i] = min_anc[i] = sdom[i] = i;for( int i = n;i > 1;i -- ) {int u = id[i];if( ! dfn[u] ) continue;int t = n;for( int j = 0;j < rG.g[u].size();j ++ ) {int v = rG.g[u][j];if( dfn[v] < dfn[u] )t = min( t, dfn[v] );else {find( v );t = min( t, dfn[sdom[min_anc[v]]] );}}sdom[u] = id[t];anc[u] = fa[u];Dfs.AddEdge( sdom[u], u );} }int lca( int u, int v ) {if( ! u || ! v ) return u + v;if( dep[u] < dep[v] ) swap( u, v );for( int i = 19;~ i;i -- )if( dep[f[u][i]] >= dep[v] ) u = f[u][i];if( u == v ) return u;for( int i = 19;~ i;i -- )if( f[u][i] != f[v][i] ) u = f[u][i], v = f[v][i];return f[u][0]; }void build_dominate( int u ) {int t = 0;for( int i = 0;i < rDfs.g[u].size();i ++ ) {int v = rDfs.g[u][i];t = lca( t, v );}dep[u] = dep[t] + 1;dominate.AddEdge( t, u );f[u][0] = t;for( int i = 1;i < 20;i ++ )f[u][i] = f[f[u][i - 1]][i - 1]; }void topo() {for( int i = 1;i <= n;i ++ )for( int j = 0;j < Dfs.g[i].size();j ++ ) {int k = Dfs.g[i][j];d[k] ++;rDfs.AddEdge( k, i );}for( int i = 1;i <= n;i ++ )if( ! d[i] ) {Dfs.AddEdge( 0, i );rDfs.AddEdge( i, 0 );}q.push( 0 );while( ! q.empty() ) {int u = q.front(); q.pop();for( int i = 0;i < Dfs.g[u].size();i ++ ) {int v = Dfs.g[u][i];if( -- d[v] <= 0 ) {build_dominate( v );q.push( v );}}} }void work( int u ) {ans[u] = 1;for( int i = 0;i < dominate.g[u].size();i ++ ) {int v = dominate.g[u][i];work( v );ans[u] += ans[v];} }int main() {scanf( "%d %d", &n, &m );for( int i = 1, u, v;i <= m;i ++ ) {scanf( "%d %d", &u, &v );G.AddEdge( u, v );rG.AddEdge( v, u );}dfs( 1 );build_dfs();topo();work( 0 );for( int i = 1;i <= n;i ++ )printf( "%d ", ans[i] );return 0; }

總結(jié)

以上是生活随笔為你收集整理的【学习笔记】DAG / 一般有向图的支配树 / 灭绝树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。