支配 (圖論)

首先来介绍一些这个算法的大概步骤

1. 对图进行DFS（深度优先遍历）并求出搜索树和DFS序。这里用 ${\displaystyle dfn[x]}$表示点 ${\displaystyle x}$在dfs序中的位置。
2. 根据半必经点定理计算出所有的半必经点作为计算必经点的根据
3. 根据必经点定理修正半必经点，求出支配点。

用 idom[x] 表示点 ${\displaystyle x}$的最近支配点，用 semi[x] 表示点 ${\displaystyle x}$的半必经点。

那什么是半必经点呢？

对于一个节点 ${\displaystyle Y}$，存在某个点 ${\displaystyle X}$能够通过一系列点 ${\displaystyle p_{i}}$（不包含 ${\displaystyle X}$和 ${\displaystyle Y}$）到达点 ${\displaystyle Y}$且 ${\displaystyle \forall i\ dfn[i]>dfn[Y]}$，就称 ${\displaystyle X}$是 ${\displaystyle Y}$的半必经点，记做 semi[Y]=X

当然一个点的“半必经点” ${\displaystyle X}$会有多个，而且这些半必经点一定是搜索树中点 ${\displaystyle X}$的祖先。

对于每个点，只需要保存其半必经点中最小的一个，下文中用表示点的半必经点中值最小的点的编号。

可以更书面一点的描述这个定理：

• 对于一个节点 ${\displaystyle Y}$考虑所有能够到达它的节点，设其中一个为 ${\displaystyle X}$
• 若 ${\displaystyle dfn[X]<dfn[Y]}$，则 ${\displaystyle X}$是 ${\displaystyle Y}$的一个半必经点

• 若 ${\displaystyle dfn[X]>dfn[Y]}$，那么对于 ${\displaystyle X}$在搜索树中的祖先 ${\displaystyle Z}$(包括 ${\displaystyle X}$)，如果满足 ${\displaystyle dfn[Z]>dfn[Y]}$那么 semi[Z] 也是 ${\displaystyle Y}$的半必经点