支配结点
每个控制流图都一定有一个没有前驱的起始结点 ，这个结点是程序（或子程序）执行的假设开始点。
如果从 到结点 的所有有向边路径都经过结点 ，那么结点 是结点 的支配结点（或必经结点）， 支配 记作 。每一个结点都是自己的支配（必经）结点。
支配关系定理
在下文的引理中，默认 。 有向图的起点，亦是其所有结点的支配点；
定理 1：支配关系是自反的，反对称的，传递的。
自反性：显然，任意一个结点都是其自身的支配点。
传递性： 经过 的路径必定经过 ，经过 的路径必定经过 ，因此经过 的路径必定经过 ，即 。
反对称性： 假设 ，则任意一个到达 的路径都已经到达过 ，同时任意一个到达 的路径都已经到达过 ，矛盾。
定理 2： 在连通图中，若 ， 且 ，则有 或 。
证明： 考虑一条 的路径，若 ， 不存在支配关系，则一定存在一条不经过 的从 到 的路径，即存在一条 的路径，与 矛盾。
直接支配结点
我们将任意一个结点 的所有支配结点中，除自身外与自己距离最近的结点 称作 的直接支配点或直接必经结点（immediate dominator），记作 。 结点 的直接支配结点，即 ，具有下列性质：
- 和 不是同一个结点，
- 是 的必经结点，并且
- 不是 的其他必经结点的必经结点。
定理 2 告诉我们，除了 没有直接支配结点外，每个结点 都有唯一一个的直接支配结点。
必经结点边界
定义：如果 是 的必经结点，并且 ，则 是 的严格必经结点。
结点 的必经结点边界（dominance frontier）是所有符合下面条件的结点 的集合： 是 的前驱的必经结点，但不是 的严格必经结点。
结点5是灰色区域中所有结点的必经结点。
- 结点5的必经结点边界包括结点4、5、12、13，这些结点都是从以结点5为必经结点的区域(包括结点5的灰色范围)到不以结点5为严格必经结点的区域（包括结点5的白色范围）的边的目标结点。
- 的必经结点边界中的任何一个结点也是两条非相交路径的汇合点，即从 来的路径和从根结点来的路径的汇合点。
- 汇合路径的另一个例子是路径 和路径 汇合。
必经结点边界的应用：只要结点 包含某个变量 的一个定值，则 的必经结点边界中的任何结点 都需要有一个 的 函数。由于 函数本身也是一种定值，我们必须迭代地应用必经结点边界，直到再没有结点需要 函数为止。
支配结点树
支配结点树，简称支配树。让我们来画这样一个图，图中包含流图的每个结点，并且对每个结点 ，有 一条从 到 的边。
根据支配关系的传递性和反对称性，我们知道支配树的边一定不会构成环，因此我们得到的图事实上是一棵树。我们称这颗树为原图的支配树（dominator tree），或必经节点树。
求支配结点
结点删除法
一个和定义等价的结论：如果我们删去图中的某一个结点后，有一些结点变得不可到达，那么这个被删去的结点支配这些变得不可到达的结点。
因此我们只要尝试将每一个结点删去后 dfs 即可，代码复杂度为 。下面给出核心代码。
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);
}
}
}
}
|
数据流迭代法
数据流迭代法是在程序的流程图的结点上列出数据流方程并不断迭代求解，从而求得程序的某些点的数据流值的一种方法。令 是 的所有必经结点的集合，这个问题中，数据流方程为：
其中 定义为 的前驱结点组成的点集。这个方程可以通过支配关系的传递性得到。
翻译成人话就是，一个点的支配点的点集为它所有前驱结点的支配点集的交集，再并上它本身。根据这个方程将每个结点上的支配点集不断迭代直至答案不变即可。
为了提高效率，我们希望每轮迭代时，当前迭代的结点的所有前驱结点尽可能都已经执行完了这次迭代，因此我们要利用深度优先排序得出这个图的逆后序，根据这个顺序进行迭代。
下面是核心代码的参考实现。这里需要预先处理每个点的前驱结点集和图的逆后序。
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);
}
}
}
}
|
不难看出上述算法的复杂度为 。
求支配树
朴素算法
朴素算法的基本思路就是根据 dom 关系求解。
不妨考虑某个结点的支配点集 ，则一定存在一条路径 。显然 的直接支配点为 。因此直接支配点的定义等价于：
对于一个结点 的支配点集 ，若 满足 ，则 。
因此，利用前文所述的算法得到每个结点的支配点集之后，我们根据上述定义便能很轻松地得到每个点的直接支配点，从而构造出支配树。下面给出参考代码。
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 的支配树。
引理 3： 在有向图上， 当且仅当 。
证明： 首先来证明充分性。考虑任意一条从 到 的路径都一定经过一个结点 ，而 支配这个结点，因此任意一条从 到 的路径都一定经过 ，因此我们得到 。
然后是必要性。如果 ， 不支配 ，则一定有一条不经过 的路径 ，因此 不支配 。
我们发现， 的支配点一定是其所有前驱结点在支配树上的公共祖先，那么显然 的直接支配点是所有前驱结点在支配树上的 LCA。考虑倍增求解 LCA 可以支持每次添加一个结点，上述算法显然是可行的。
Lengauer–Tarjan 算法
Lengauer–Tarjan 算法是求解支配树最有名的算法之一，可以在 的时间复杂度内求出一个有向图的支配树。这一算法引入了 半支配点 的概念，并通过半支配点辅助求得直接支配点。
约定
首先，我们从 出发对这个有向图进行 dfs ，所经过的点和边形成了一颗树 。我们称走过的边为树边，其余的为非树边；令 表示结点 被第几个遍历到；定义 当且仅当 。
半支配点
设结点 满足：
是满足这个条件的所有结点的集合。则 中 最小的结点 ，称为结点 的半支配点。通俗的理解是，半支配结点是 的任意两个前驱的公共祖先中最高的那一个。形式化的说， 的半支配点 定义为： 我们发现半支配点有一些有用的性质：
性质 1： 对于任意结点 ，。
证明： 根据定义不难发现， 在 上的父亲 也满足成为半支配点的条件，且 ，因此任何大于 的结点都不可能成为其半支配点。
性质 2： 对于任意结点 ， 是其在 上的祖先。
证明： 上从 到 的路径对应了原图上的一条路径，则 必定在这个路径上。
性质 3： 对于任意结点 ， 是其在 上的祖先。
证明： 假设 不是 的祖先，那么 也一定满足成为半支配点的条件，且 ，这与 的定义矛盾。
性质 4： 对于任意结点 ， 是 的祖先。
证明： 考虑可以从 到 再从定义中的路径走到 。根据定义， 到 的路径上的点均不支配 ，故 一定是 的祖先。
性质 5： 对于任意结点 满足 是 的祖先，则要么有 是 的祖先，要么 是 的祖先。
证明： 对于任意在 和 之间的结点 ，根据直接支配点的定义，一定存在一条不经过 的，从 到 再到 的路径。因此这些结点 一定不是 ，因此 要么是 的后代，要么是 的祖先。
根据以上引理，我们可以得到以下定理：
定理 4： 一个点 的半支配点满足.
即考虑 的所有前驱 。
- 如果 是 在生成树中的真祖先(有 ，则 是 的候选。
- 如果 不是 的祖先(有 ，则对 的每个祖先 (或者 )，令 成为 的候选。
所有这些候选中，具有最低 的结点就是 的半支配结点。
证明： 令 等于上式右侧。
我们首先证明 。根据引理 7 我们知道这个命题等价于证明上述的两种都满足成为半支配点的条件。 是 的前驱时的情况是显然的，对于后半部分，我们考虑将半支配点定义中所述路径 和 上的一条满足 的路径 以及路径 拼接，从而我们构造出一条满足半支配点定义的路径。
然后我们证明 。考虑 到其半支配点的定义中所述路径 。不难看出 和 分别对应了定义中的两个选取方法。若 ，则存在有向边 ，根据引理 7 即可得证；若 ，令 是满足 且 是 在 上祖先的最小数。考虑到 满足上述条件，这样的 一定存在。
考虑证明 是满足成为 半支配点条件的一条路径，即证明 。若不是，则令 为满足 中使 最小的数，根据引理 11 我们知道 是 的祖先，这和 的定义矛盾。于是 。综上 ，故 。
根据定理 4 我们便可以求出每个点的半支配点了。不难发现计算半支配点的复杂度瓶颈在第二种情况上，我们考虑利用带权并查集优化，每次路径压缩时更新最小值即可。
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
可是我还是不知道半支配点有什么用！
我们考虑在 上对每一个 加入 的有向边。根据引理 9，新得到的这张图 一定是有向无环图；又根据引理 10，我们还发现这样加边不会改变支配关系，因此我们把原图转化为了一张 DAG，利用上文的算法求解即可。
通过半支配点求解
建一堆图也太不优雅了！
定理 5： 对于任意节点 ，若 上从 到 的路径上的任意节点 都满足 ，则 。
证明： 根据引理 10 我们知道 是 或其祖先，因此只需证明 。
考虑任意一条 到 的路径 ，我们需要证明 一定在 中。令 为 中最后一个满足 的节点。如果 不存在则必有 ，否则令 是 中 之后在 DFS 树中从 到 的路径上的第一个点。
我们接下来证明 。考虑 上 到 的路径 ，若不成立，则存在 。此时一定存在某个 满足 是 的祖先。由 的取值可知 ，于是 也在 DFS 树中从 到 的路径上，与 的定义矛盾，因此 ，结合定理的条件有 ，即路径 包含 。
定理 6： 对于任意节点 ， 上从 到 的路径上的所有节点中半支配点最小的节点 一定满足 和 。
证明： 考虑到 本身也满足 的条件，因此 。
由于 是 在 上的祖先，由引理 11 可知 也是 的祖先，因此只需证明 支配 。
考虑任意一条 到 的路径 ，我们需要证明 一定在 中。令 为 中最后一个满足 的节点。如果 不存在则必有 ，否则令 是 中 之后在 DFS 树中从 到 的路径上的第一个点。
与定理 2 的证明过程同理，我们可以得到 。根据引理 10 有 。至此，由 的定义可知 不能是 的后代；另一方面， 不能既是 的后代也是 的祖先，否则沿 DFS 树从 到 再沿 P 走到 ，最后沿 DFS 树走到 的这条路径不经过 ，与支配点的定义矛盾。因此 ，即 包含 。
根据以上两个定理我们能够得到 与 之间的关系。
令 是满足 在 与 之间的结点的所有节点中， 最小的一个节点，那么：
只要对上面求解半支配点的代码稍作修改即可。
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]];
}
}
}
|
结点5是灰色区域中所有结点的必经结点。