支配樹

前言

1959 年，「支配」這一概念由 Reese T. Prosser 在一篇關於網絡流的論文中提出，但並未提出具體的求解算法；直到 1969 年，Edward S. Lowry 和 C. W. Medlock 才首次提出了有效的求解算法。而目前使用最為廣泛的 Lengauer–Tarjan 算法則由 Lengauer 和 Tarjan 於 1979 年在一篇論文中提出。

在 OI 界中，支配樹的概念最早在 ZJOI2012 災難中被引入，當時也被稱為「滅絕樹」；陳孫立也在 2020 年的國家集訓隊論文中介紹了這一算法。

目前支配樹在競賽界並不流行，其相關習題並不多見；但支配樹在工業上，尤其是編譯器相關領域，已有廣泛運用。

本文將介紹支配樹的概念及幾種求解方法。

支配關係

我們在任意的一個有向圖上欽定一個入口結點 $s$，對於一個結點 $u$，若從 $s$ 到 $u$ 的每一條路徑都經過某一個結點 $v$，那麼我們稱 $v$ 支配 $u$，也稱 $v$ 是 $u$ 的一個 支配點，記作 $v\ dom\ u$。

對於從 $s$ 出發無法到達的結點，討論其支配關係是沒有意義的，因此在沒有特殊説明的情況下，本文默認 $s$ 能到達圖上任何一個結點。

例如這張有向圖中，$2$ 被 $1$ 支配，$3$ 被 $1, 2$ 支配，4 被 $1, 2, 3$ 支配，5 被 $1, 2$ 支配，etc。

引理

在下文的引理中，默認 $u, v, w\ne s$

引理 1： $s$ 是其所有結點的支配點；任意一個結點都是其自身的支配點。

證明： 顯然任何一條從 $s$ 到 $u$ 的路徑都必須經過 $s$ 和 $u$ 這兩個結點。

引理 2： 僅考慮簡單路徑得出的支配關係與考慮所有路徑得出的關係相同。

證明： 對於非簡單路徑，我們設兩次經過某個結點之間經過的所有結點的點集為 $S$，若將 $S$ 中的結點刪去，便能將每個非簡單路徑與一個簡單路徑對應。

在 $S$ 中，在非簡單路徑而不在簡單路徑上的點一定不可能成為支配點，因為至少有一條 $s$ 到 $u$ 的簡單路徑不包括這個點；同時在簡單路徑和非簡單路徑上的點只需在簡單路徑上討論即可。

綜上，刪去非簡單路徑對支配關係沒有影響。

引理 3： 如果 $u$ $dom$ $v$，$v$ $dom$ $w$，則 $u$ $dom$ $w$。

證明： 經過 $w$ 的路徑必定經過 $v$，經過 $v$ 的路徑必定經過 $u$，因此經過 $w$ 的路徑必定經過 $u$，即 $u \ dom \ w$。

引理 4： 如果 $u \ dom \ v$，$v \ dom\ u$，則 $u=v$。

證明： 假設 $u \ne v$，則任意一個到達 $v$ 的路徑都已經到達過 $u$，同時任意一個到達 $u$ 的路徑都已經到達過 $v$，矛盾。

引理 5： 若 $u \ne v \ne w$,$u \ dom \ w$ 且 $v \ dom \ w$，則有 $u \ dom \ v$ 或 $v \ dom \ u$。

證明： 考慮一條 $s \rightarrow \dots \rightarrow u \rightarrow \dots \rightarrow v \rightarrow \dots \rightarrow w$ 的路徑，若 $u$,$v$ 不存在支配關係，則一定存在一條不經過 $u$ 的從 $s$ 到 $v$ 的路徑，即存在一條 $s \rightarrow \dots \rightarrow v \rightarrow \dots \rightarrow w$ 的路徑，與 $u\ dom\ w$ 矛盾。

求解支配關係

結點刪除法

一個和定義等價的結論：如果我們刪去圖中的某一個結點後，有一些結點變得不可到達，那麼這個被刪去的結點支配這些變得不可到達的結點。

因此我們只要嘗試將每一個結點刪去後 dfs 即可，代碼複雜度為 $O(n^3)$。下面給出核心代碼。

// 假設圖中有 n 個結點, 起始點 s = 1
std::bitset<N> vis;
std::vector<int> edge[N];
std::vector<int> dom[N];

void dfs(int u, int del) {
  vis[u] = true;
  for (int v : edge[u]) {
    if (v == del or vis[v]) {
      continue;
    }
    dfs(v, del);
  }
}

void getdom() {
  for (int i = 2; i <= n; ++i) {
    vis.reset();
    dfs(1, i);
    for (int j = 1; j <= n; ++j) {
      if (!vis[j]) {
        dom[j].push_back(i);
      }
    }
  }
}

數據流迭代法

數據流迭代法也是 OI 中不常見的一個知識點，這裏先做簡要介紹。

數據流分析是編譯原理中的概念，用於分析數據如何在程序執行路徑上的流動；而數據流迭代法是在程序的流程圖的結點上列出方程並不斷迭代求解，從而求得程序的某些點的數據流值的一種方法。這裏我們就是把有向圖看成了一個程序流程圖。

這個問題中，方程為：

\[ dom(u)=\{u\} \cup \left(\bigcap_{v\in pre(u)}{dom(v)}\right) \]

其中 $pre(u)$ 定義為 $u$ 的前驅結點組成的點集。這個方程可以通過引理 3 得到。

翻譯成人話就是，一個點的支配點的點集為它所有前驅結點的支配點集的交集，再並上它本身。根據這個方程將每個結點上的支配點集不斷迭代直至答案不變即可。

為了提高效率，我們希望每輪迭代時，當前迭代的結點的所有前驅結點儘可能都已經執行完了這次迭代，因此我們要利用深度有限排序得出這個圖的逆後序，根據這個順序進行迭代。

下面給出核心代碼的參考實現。這裏需要預先處理每個點的前驅結點集和圖的逆後序，但這不是本文討論的主要內容，故這裏不提供參考實現。

std::vector<int> pre[N];  // 每個結點的前驅結點
std::vector<int> ord;     // 圖的逆後序
std::bitset<N> dom[N];
std::vector<int> Dom[N];

void getdom() {
  dom[1][1] = true;
  flag = true;
  while (flag) {
    flag = false;
    for (int u : ord) {
      std::bitset<N> tmp;
      tmp[u] = true;
      for (int v : pre[u]) {
        tmp &= dom[v];
      }
      if (tmp != dom[u]) {
        dom[u] = tmp;
        flag = true;
      }
    }
  }
  for (int i = 2; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      if (dom[i][j]) {
        Dom[i].push_back(j);
      }
    }
  }
}

不難看出上述算法的複雜度為 $O(n^2)$。

支配樹

上一節我們發現，除 $s$ 外，一個點的支配點至少有兩個，$s$ 和其自身。

我們將任意一個結點 $u$ 的支配點中，除自身外與自己距離最近的結點 $v$ 稱作 $u$ 的直接支配點，記作 $idom(u) = v$。顯然除了 $s$ 沒有直接支配點外，每個結點都有唯一一個直接支配點。

我們考慮對於除 $s$ 外每一個結點 $u$ 從 $idom(u)$ 向 $u$ 連邊，便構成了一個有 $n$ 個結點，$n - 1$ 條邊的有向圖。根據引理 3 和引理 4，我們知道支配關係一定不會構成循環，也就是這些邊一定不構成環，因此我們得到的圖事實上是一棵樹。我們稱這顆樹為原圖的 支配樹。

求解支配樹

根據 dom 求解

不妨考慮某個結點的支配點集 $\{s_1, s_2, \dots, s_k\}$，則一定存在一條路徑 $s \rightarrow \dots \rightarrow s_1 \rightarrow \dots \rightarrow s_2 \rightarrow \dots \rightarrow \dots \rightarrow s_k \rightarrow\dots \rightarrow u$。顯然 $u$ 的直接支配點為 $s_k$。因此直接支配點的定義等價於：

對於一個結點 $u$ 的支配點集 $S$，若 $v \in S$ 滿足 $\forall w \in S\setminus\{u,v\}, w\ dom \ v$，則 $idom(u)=v$。

因此，利用前文所述的算法得到每個結點的支配點集之後，我們根據上述定義便能很輕鬆地得到每個點的直接支配點，從而構造出支配樹。下面給出參考代碼。

std::bitset<N> dom[N];
std::vector<int> Dom[N];
int idom[N];

void getidom() {
  for (int u = 2; u <= n; ++u) {
    for (int v : Dom[u]) {
      std::bitset<N> tmp = (dom[v] & dom[u]) ^ dom[u];
      if (tmp.count() == 1 and tmp[u]) {
        idom[u] = v;
        break;
      }
    }
  }
  for (int u = 2; u <= n; ++u) {
    e[idom[u]].push_back(u);
  }
}

樹上的特例

顯然樹型圖的支配樹就是它本身。

DAG 上的特例

我們發現 DAG 有一個很好的性質：根據拓撲序求解，先求得的解不會對後續的解產生影響。我們可以利用這個特點快速求得 DAG 的支配樹。

引理 6： 在有向圖上，$v\ dom\ u$ 當且僅當 $\forall w \in pre(u), v\ dom \ w$。

證明： 首先來證明充分性。考慮任意一條從 $s$ 到 $u$ 的路徑都一定經過一個結點 $w \in pre(u)$，而 $v$ 支配這個結點，因此任意一條從 $s$ 到 $u$ 的路徑都一定經過 $v$，因此我們得到 $v \ dom \ u$。

然後是必要性。如果 $\exists w\in pre(u)$，$v$ 不支配 $w$，則一定有一條不經過 $v$ 的路徑 $s \rightarrow \cdots \rightarrow w \rightarrow \cdots \rightarrow u$，因此 $v$ 不支配 $u$。

我們發現，$u$ 的支配點一定是其所有前驅結點在支配樹上的公共祖先，那麼顯然 $u$ 的直接支配點是所有前驅結點在支配樹上的 LCA。考慮倍增求解 LCA 可以支持每次添加一個結點，上述算法顯然是可行的。

下面給出參考實現：

std::stack<int> sta;
vector<int> e[N], g[N], tree[N];  // g 是原圖的反圖, tree 是支配樹
int in[N], tpn[N], dep[N], idom[N];
int fth[N][17];

void topo() {
  for (int i = 1; i <= n; ++i) {
    if (!in[i]) {
      sta.push(i);
    }
  }
  while (!sta.empty()) {
    int u = sta.top();
    sta.pop();
    tpn[++tot] = u;
    for (int v : e[u]) {
      --in[v];
      if (!in[v]) {
        sta.push(v);
      }
    }
  }
}

int lca(int u, int v) {
  if (dep[u] < dep[v]) {
    std::swap(u, v);
  }
  for (int i = 15; i >= 0; --i) {
    if (dep[fth[u][i]] >= dep[v]) {
      u = fth[u][i];
    }
  }
  if (u == v) {
    return u;
  }
  for (int i = 15; i >= 0; --i) {
    if (fth[u][i] != fth[v][i]) {
      u = fth[u][i];
      v = fth[v][i];
    }
  }
  return fth[u][0];
}

void build() {
  topo();
  for (int i = 1; i <= n; ++i) {
    int u = tpn[i], v = g[u][0];
    for (int j = 1, q = g[u].size(); j < q; ++j) {
      v = lca(v, g[u][j]);
    }
    idom[u] = v;
    tree[v].push_back(u);
    fth[u][0] = v;
    dep[u] = dep[v] + 1;
    for (int i = 1; i <= 15; ++i) {
      fth[u][i] = fth[fth[u][i - 1]][i - 1];
    }
  }
}

Lengauer–Tarjan 算法

Lengauer–Tarjan 算法是求解支配樹最有名的算法之一，可以在 $O(n\alpha(n, m))$ 的時間複雜度內求出一個有向圖的支配樹。這一算法引入了 半支配點 的概念，並通過半支配點輔助求得直接支配點。

約定

首先，我們從 $s$ 出發對這個有向圖進行 dfs，所經過的點和邊形成了一顆樹 $T$。我們稱走過的邊為樹邊，其餘的為非樹邊；令 $dfn(u)$ 表示結點 $u$ 被第幾個遍歷到；定義 $u<v$ 當且僅當 $dfn(u) < dfn(v)$。

半支配點

一個結點 $u$ 的半支配點，是滿足從這個結點 $v$ 出發有一條路徑，路徑上除了 $u, v$ 之外每個結點都大於 $u$ 的結點中最小的那一個。形式化的説，$u$ 的半支配點 $sdom(u)$ 定義為：

$sdom(u) = \min(v|\exists v=v_0 \rightarrow v_1 \rightarrow\dots \rightarrow v_k = u, \forall 1\le i\le k - 1, v_i > u)$

我們發現半支配點有一些有用的性質：

引理 7： 對於任意結點 $u$，$sdom(u) < u$。

證明： 根據定義不難發現，$u$ 在 $T$ 上的父親 $fa(u)$ 也滿足成為半支配點的條件，且 $fa(u) < u$，因此任何大於 $u$ 的結點都不可能成為其半支配點。

引理 8： 對於任意結點 $u$，$idom(u)$ 是其在 $T$ 上的祖先。

證明： $T$ 上從 $s$ 到 $u$ 的路徑對應了原圖上的一條路徑，則 $idom(u)$ 必定在這個路徑上。

引理 9： 對於任意結點 $u$，$sdom(u)$ 是其在 $T$ 上的祖先。

證明： 假設 $sdom(u)$ 不是 $u$ 的祖先，那麼 $sdom(u)$ 不可能連向任何 $\mathrm{dfs}$ 序大於等於 $u$ 的結點（否則這個點應在 $sdom(u)$ 的子樹內而非其他子樹內），矛盾。

引理 10： 對於任意結點 $u$，$idom(u)$ 是 $sdom(u)$ 的祖先。

證明： 考慮可以從 $s$ 到 $sdom(u)$ 再從定義中的路徑走到 $u$。根據定義，$sdom(u)$ 到 $u$ 的路徑上的點均不支配 $u$，故 $idom(u)$ 一定是 $sdom(u)$ 的祖先。

引理 11： 對於任意結點 $u \ne v$ 滿足 $v$ 是 $u$ 的祖先，則要麼有 $v$ 是 $idom(u)$ 的祖先，要麼 $idom(u)$ 是 $idom(v)$ 的祖先。

證明： 對於任意在 $v$ 和 $idom(v)$ 之間的結點 $w$，根據直接支配點的定義，一定存在一條不經過 $w$ 的，從 $s$ 到 $idom(v)$ 再到 $v$ 的路徑。因此這些結點 $w$ 一定不是 $idom(u)$，因此 $idom(u)$ 要麼是 $v$ 的後代，要麼是 $idom(v)$ 的祖先。

根據以上引理，我們可以得到以下定理：

定理 1： 一個點 $u$ 的半支配點是其前驅與其支配點在 $T$ 上的，大於 $u$ 的所有祖先的半支配點中最小的節點。形式化地説，$sdom(u)=\min(\{v|\exists v \rightarrow u, v < u) \} \cup \{sdom(w) | w > u\ and\ \exists w \rightarrow \dots \rightarrow v \rightarrow u \})$。

證明： 令 $x$ 等於上式右側。

我們首先證明 $sdom(u) \le x$。根據引理 7 我們知道這個命題等價於證明上述的兩種都滿足成為半支配點的條件。$x$ 是 $u$ 的前驅時的情況是顯然的，對於後半部分，我們考慮將半支配點定義中所述路徑 $x=v_0\rightarrow\dots\rightarrow v_j=w$ 和 $T$ 上的一條滿足 $\forall i\in[j, k-1], v_i\ge w > u$ 的路徑 $w=v_j \rightarrow\dots\rightarrow v_k=v$ 以及路徑 $v \rightarrow u$ 拼接，從而我們構造出一條滿足半支配點定義的路徑。

然後我們證明 $sdom(u)\ge x$。考慮 $u$ 到其半支配點的定義中所述路徑 $sdom(u)=v_0\rightarrow v_1 \rightarrow\dots\rightarrow v_k=u$。不難看出 $k=1$ 和 $k > 1$ 分別對應了定義中的兩個選取方法。若 $k = 1$，則存在有向邊 $sdom(u) \rightarrow u$，根據引理 7 即可得證；若 $k>1$，令 $j$ 是滿足 $ j\ge 1 $ 且 $v_j$ 是 $v_{k-1}$ 在 $T$ 上祖先的最小數。考慮到 $k$ 滿足上述條件，這樣的 $j$ 一定存在。

考慮證明 $v_0 \rightarrow \dots \rightarrow v_j$ 是滿足成為 $v_j$ 半支配點條件的一條路徑，即證明 $\forall i \in [1, j), v_i>v_j$。若不是，則令 $i$ 為滿足 $v_i < v_j$ 中使 $v_i$ 最小的數，根據引理 11 我們知道 $v_i$ 是 $v_j$ 的祖先，這和 $j$ 的定義矛盾。於是 $sdom(v_j)\le sdom(u)$。綜上 $sdom(u) \le x$，故 $x=sdom(u)$。

根據定理 1 我們便可以求出每個點的半支配點了。不難發現計算半支配點的複雜度瓶頸在第二種情況上，我們考慮利用帶權並查集優化，每次路徑壓縮時更新最小值即可。

void dfs(int u) {
  dfn[u] = ++dfc;
  pos[dfc] = u;
  for (int i = h[0][u]; i; i = e[i].x) {
    int v = e[i].v;
    if (!dfn[v]) {
      dfs(v);
      fth[v] = u;
    }
  }
}

int find(int x) {
  if (fa[x] == x) {
    return x;
  }
  int tmp = fa[x];
  fa[x] = find(fa[x]);
  if (dfn[sdm[mn[tmp]]] < dfn[sdm[mn[x]]]) {
    mn[x] = mn[tmp];
  }
  return fa[x];
}

void getsdom() {
  dfs(1);
  for (int i = 1; i <= n; ++i) {
    mn[i] = fa[i] = sdm[i] = i;
  }
  for (int i = dfc; i >= 2; --i) {
    int u = pos[i], res = INF;
    for (int j = h[1][u]; j; j = e[j].x) {
      int v = e[j].v;
      if (!dfn[v]) {
        continue;
      }
      find(v);
      if (dfn[v] < dfn[u]) {
        res = std::min(res, dfn[v]);
      } else {
        res = std::min(res, dfn[sdm[mn[v]]]);
      }
    }
    sdm[u] = pos[res];
    fa[u] = fth[u];
  }
}

求解直接支配點

轉化為 DAG

可是我還是不知道半支配點有什麼用！

我們考慮在 $T$ 上對每一個 $u$ 加入 $sdom(u) \rightarrow u$ 的有向邊。根據引理 9，新得到的這張圖 $G$ 一定是有向無環圖；又根據引理 10，我們還發現這樣加邊不會改變支配關係，因此我們把原圖轉化為了一張 DAG，利用上文的算法求解即可。

通過半支配點求解

建一堆圖也太不優雅了！

定理 2： 對於任意節點 $u$，若 $T$ 上從 $sdom(u)$ 到 $w$ 的路徑上的任意節點 $v$ 都滿足 $sdom(v)\ge sdom(w)$，則 $idom(u) =sdom(u)$。

證明： 根據引理 10 我們知道 $idom(u)$ 是 $sdom(u)$ 或其祖先，因此只需證明 $sdom(u) \ dom \ u$。

考慮任意一條 $s$ 到 $u$ 的路徑 $P$，我們需要證明 $sdom(u)$ 一定在 $P$ 中。令 $v$ 為 $P$ 中最後一個滿足 $v<sdom(u)$ 的節點。如果 $v$ 不存在則必有 $sdom(u)=idom(u) =s$，否則令 $w$ 是 $P$ 中 $v$ 之後在 DFS 樹中從 $sdom(u)$ 到 $u$ 的路徑上的第一個點。

我們接下來證明 $sdom(w)\le v <sdom(v)$。考慮 $T$ 上 $v$ 到 $w$ 的路徑 $v = v_0 \rightarrow \dots v_k = w$，若不成立，則存在 $i\in[1, k- 1], v_i < w$。此時一定存在某個 $j\in [i, k - 1]$ 滿足 $v_j$ 是 $w$ 的祖先。由 $v$ 的取值可知 $sdom(u)\le v_j$，於是 $v_j$ 也在 DFS 樹中從 $sdom(u)$ 到 $u$ 的路徑上，與 $w$ 的定義矛盾，因此 $sdom(w)\le v < sdom(v)$，結合定理的條件有 $y=sdom(u)$，即路徑 $P$ 包含 $sdom(u)$。

定理 3： 對於任意節點 $u$，$T$ 上從 $sdom(u)$ 到 $u$ 的路徑上的所有節點中半支配點最小的節點 $v$ 一定滿足 $sdom(v)\le sdom(u)$ 和 $idom(v) = idom(u)$。

證明： 考慮到 $u$ 本身也滿足 $v$ 的條件，因此 $sdom(v)\le sdom(u)$。

由於 $idom(u)$ 是 $v$ 在 $T$ 上的祖先，由引理 11 可知 $idom(u)$ 也是 $idom(v)$ 的祖先，因此只需證明 $idom(v)$ 支配 $u$。

考慮任意一條 $s$ 到 $u$ 的路徑 $P$，我們需要證明 $sdom(u)$ 一定在 $P$ 中。令 $x$ 為 $P$ 中最後一個滿足 $x<sdom(u)$ 的節點。如果 $x$ 不存在則必有 $sdom(u)=idom(u) =s$，否則令 $y$ 是 $P$ 中 $x$ 之後在 DFS 樹中從 $sdom(u)$ 到 $u$ 的路徑上的第一個點。

與定理 2 的證明過程同理，我們可以得到 $sdom(y) \le x$。根據引理 10 有 $sdom(y)\le x<idom(v) \le sdom(v)$。至此，由 $v$ 的定義可知 $y$ 不能是 $sdom(u)$ 的後代；另一方面，$y$ 不能既是 $idom(v)$ 的後代也是 $v$ 的祖先，否則沿 DFS 樹從 $s$ 到 $sdom(y)$ 再沿 P 走到 $y$，最後沿 DFS 樹走到 $v$ 的這條路徑不經過 $idom(v)$，與支配點的定義矛盾。因此 $y=idom(v)$，即 $P$ 包含 $idom(v)$。

根據以上兩個定理我們能夠得到 $sdom(u)$ 與 $idom(u)$ 之間的關係。

令 $v$ 是滿足 $v$ 在 $sdom(u)$ 與 $u$ 之間的結點的所有節點中，$sdom(v)$ 最小的一個節點，那麼：

\[ idom(u) = \left\{ \begin{aligned} & sdom(u), &\text{if}\ sdom(u) = sdom(v) \\ &idom(v), &\text{otherwise} \end{aligned} \right. \]

只要對上面求解半支配點的代碼稍作修改即可。

struct E {
  int v, x;
} e[MAX * 4];

int h[3][MAX * 2];

int dfc, tot, n, m, u, v;
int fa[MAX], fth[MAX], pos[MAX], mn[MAX], idm[MAX], sdm[MAX], dfn[MAX],
    ans[MAX];

void add(int x, int u, int v) {
  e[++tot] = {v, h[x][u]};
  h[x][u] = tot;
}

void dfs(int u) {
  dfn[u] = ++dfc;
  pos[dfc] = u;
  for (int i = h[0][u]; i; i = e[i].x) {
    int v = e[i].v;
    if (!dfn[v]) {
      dfs(v);
      fth[v] = u;
    }
  }
}

int find(int x) {
  if (fa[x] == x) {
    return x;
  }
  int tmp = fa[x];
  fa[x] = find(fa[x]);
  if (dfn[sdm[mn[tmp]]] < dfn[sdm[mn[x]]]) {
    mn[x] = mn[tmp];
  }
  return fa[x];
}

void tar(int st) {
  dfs(st);
  for (int i = 1; i <= n; ++i) {
    fa[i] = sdm[i] = mn[i] = i;
  }
  for (int i = dfc; i >= 2; --i) {
    int u = pos[i], res = INF;
    for (int j = h[1][u]; j; j = e[j].x) {
      int v = e[j].v;
      if (!dfn[v]) {
        continue;
      }
      find(v);
      if (dfn[v] < dfn[u]) {
        res = std::min(res, dfn[v]);
      } else {
        res = std::min(res, dfn[sdm[mn[v]]]);
      }
    }
    sdm[u] = pos[res];
    fa[u] = fth[u];
    add(2, sdm[u], u);
    u = fth[u];
    for (int j = h[2][u]; j; j = e[j].x) {
      int v = e[j].v;
      find(v);
      if (sdm[mn[v]] == u) {
        idm[v] = u;
      } else {
        idm[v] = mn[v];
      }
    }
    h[2][u] = 0;
  }
  for (int i = 2; i <= dfc; ++i) {
    int u = pos[i];
    if (idm[u] != sdm[u]) {
      idm[u] = idm[idm[u]];
    }
  }
}

例題

洛谷 P5180【模板】支配樹

可以僅求解支配關係，求解過程中記錄各個點支配了多少節點，也可以建出支配樹求解每個節點的 size。

這裏給出後一種解法的代碼。

參考代碼

#include <bits/stdc++.h>
using std::cin;
using std::cout;
const int MAX = 3e5 + 5;
const int INF = 0x5ffffff;

struct E {
  int v, x;
} e[MAX * 4];

int n, m, u, v, tot, dfc;
int ans[MAX], dfn[MAX], pos[MAX], sdm[MAX], idm[MAX], fa[MAX], mn[MAX],
    fth[MAX];
int h[3][MAX * 2];

void add(int x, int u, int v) {
  e[++tot] = {v, h[x][u]};
  h[x][u] = tot;
}

void dfs(int u) {
  dfn[u] = ++dfc;
  pos[dfc] = u;
  for (int i = h[0][u]; i; i = e[i].x) {
    int v = e[i].v;
    if (!dfn[v]) {
      dfs(v);
      fth[v] = u;
    }
  }
}

int find(int x) {
  if (fa[x] == x) {
    return x;
  }
  int tmp = fa[x];
  fa[x] = find(fa[x]);
  if (dfn[sdm[mn[tmp]]] < dfn[sdm[mn[x]]]) {
    mn[x] = mn[tmp];
  }
  return fa[x];
}

void tar(int st) {
  dfs(st);
  for (int i = 1; i <= n; ++i) {
    mn[i] = fa[i] = sdm[i] = i;
  }
  for (int i = dfc; i >= 2; --i) {
    int u = pos[i], res = INF;
    for (int j = h[1][u]; j; j = e[j].x) {
      int v = e[j].v;
      if (!dfn[v]) {
        continue;
      }
      find(v);
      if (dfn[v] < dfn[u]) {
        res = std::min(res, dfn[v]);
      } else {
        res = std::min(res, dfn[sdm[mn[v]]]);
      }
    }
    sdm[u] = pos[res];
    fa[u] = fth[u];
    add(2, sdm[u], u);
    u = fth[u];
    for (int j = h[2][u]; j; j = e[j].x) {
      int v = e[j].v;
      find(v);
      if (u == sdm[mn[v]]) {
        idm[v] = u;
      } else {
        idm[v] = mn[v];
      }
    }
    h[2][u] = 0;
  }
  for (int i = 2; i <= dfc; ++i) {
    int u = pos[i];
    if (idm[u] != sdm[u]) {
      idm[u] = idm[idm[u]];
    }
  }
  for (int i = dfc; i >= 2; --i) {
    ++ans[pos[i]];
    ans[idm[pos[i]]] += ans[pos[i]];
  }
  ++ans[1];
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    cin >> u >> v;
    add(0, u, v);
    add(1, v, u);
  }
  tar(1);
  for (int i = 1; i <= n; ++i) {
    cout << ans[i] << ' ';
  }
}

ZJOI2012 災難

在 DAG 上求支配樹然後求節點 size 即可。

參考代碼

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::stack;
using std::vector;

const int MAX = 65536;
int n, x, tot;
int d[MAX], w[MAX], siz[MAX], p[MAX], f[MAX][17];
vector<int> e[MAX], g[MAX], h[MAX];
stack<int> s;

void topo() {
  s.push(0);
  for (int i = 1; i <= n; ++i) {
    if (!w[i]) {
      e[0].push_back(i);
      g[i].push_back(0);
      ++w[i];
    }
  }
  while (!s.empty()) {
    int x = s.top();
    s.pop();
    p[++tot] = x;
    for (int i : e[x]) {
      --w[i];
      if (!w[i]) {
        s.push(i);
      }
    }
  }
}

int lca(int u, int v) {
  if (d[u] < d[v]) {
    std::swap(u, v);
  }
  for (int i = 15; i >= 0; --i) {
    if (d[f[u][i]] >= d[v]) {
      u = f[u][i];
    }
  }
  if (u == v) {
    return u;
  }
  for (int i = 15; i >= 0; --i) {
    if (f[u][i] != f[v][i]) {
      u = f[u][i];
      v = f[v][i];
    }
  }
  return f[u][0];
}

void dfs(int x) {
  siz[x] = 1;
  for (int i : h[x]) {
    dfs(i);
    siz[x] += siz[i];
  }
}

void build() {
  for (int i = 2; i <= n + 1; ++i) {
    int x = p[i], y = g[x][0];
    for (int j = 1, q = g[x].size(); j < q; ++j) {
      y = lca(y, g[x][j]);
    }
    h[y].push_back(x);
    d[x] = d[y] + 1;
    f[x][0] = y;
    for (int i = 1; i <= 15; ++i) {
      f[x][i] = f[f[x][i - 1]][i - 1];
    }
  }
}

int main() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    while (true) {
      cin >> x;
      if (!x) {
        break;
      }
      e[x].push_back(i);
      g[i].push_back(x);
      ++w[i];
    }
  }
  topo();
  build();
  dfs(0);
  for (int i = 1; i <= n; ++i) {
    cout << siz[i] - 1 << '\n';
  }
  return 0;
}

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用