定义
给定一张有向图与一个起点 \(s\)，如果要去掉起点 \(s\) 到某个点 \(v\) 的中间的某个点 \(u\) 后无法到达，那么称点 \(u\) 支配点 \(v\)，\(u\) 是 \(v\) 的一个支配点
- 最近支配点 \((idom[u])\)
\(u\) 的支配点中距离 \(u\) 最近的一点
- 支配树
由所有边 \(idom[u]\rightarrow u\) 构成的树。在树上，满足：
1、\(u\) 的支配点即为它的所有祖先
2、\(u\) 支配的点数即为其子树大小
即，判断一张有向图中，点 \(u\) 是否支配 \(v\) 时，即可在支配树上判断 \(u\) 是否是 \(v\) 的祖先
下面分为三中情况讨论支配树的构建
树
显然支配树就是这棵树
DAG
构建 \(DFS\) 树，\(idom[u]\) 即为图中所有一步指向它的点在 \(DFS\) 树上的 \(LCA\)
时间复杂度 \(\mathcal {O} (m\log n)\)
有向图
\(\mathcal {Lengauer\;Tarjan}\) 算法
做法略，证明略，反正我已经打 \(\mathcal {ACM}\) 了，有板子就行了o.O
代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 3e5 + 50, INF = 0x3f3f3f3f;
inline int read () {
register int x = 0, w = 1;
register char ch = getchar ();
for (; ch < '0' || ch > '9'; ch = getchar ()) if (ch == '-') w = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar ()) x = x * 10 + ch - '0';
return x * w;
}
int n, m;
int ans[maxn];
struct Edge {
int to, next;
} e[3][maxn];
int tot[3], head[3][maxn];
inline void Add (register int id, register int u, register int v) {
e[id][++ tot[id]].to = v;
e[id][tot[id]].next = head[id][u];
head[id][u] = tot[id];
}
int tic;
int fa[maxn];
int dfn[maxn], rk[maxn];
int sdom[maxn], idom[maxn];
int f[maxn], minn[maxn];
inline int Find (register int u) {
if (u == f[u]) return u;
register int rt = Find (f[u]);
if (dfn[sdom[minn[f[u]]]] < dfn[sdom[minn[u]]])
minn[u] = minn[f[u]];
return f[u] = rt;
}
inline void DFS (register int u) {
dfn[u] = ++ tic, f[u] = minn[u] = sdom[u] = rk[tic] = u;
for (register int i = head[0][u]; i; i = e[0][i].next) {
register int v = e[0][i].to;
if (! dfn[v]) fa[v] = u, DFS (v);
}
}
inline void Build (register int s) { // 起点 s
DFS (s);
for (register int i = tic; i > 1; i --) {
register int u = rk[i];
for (register int j = head[1][u]; j; j = e[1][j].next) {
register int v = e[1][j].to;
if (! dfn[v]) continue;
Find (v);
if (dfn[sdom[minn[v]]] < dfn[sdom[u]]) sdom[u] = sdom[minn[v]];
}
f[u] = fa[u], Add (2, sdom[u], u), u = fa[u];
for (register int j = head[2][u]; j; j = e[2][j].next) {
register int v = e[2][j].to;
Find (v), idom[v] = (u == sdom[minn[v]] ? u : minn[v]);
}
head[2][u] = 0;
}
for (register int i = 2; i <= tic; i ++) {
register int u = rk[i];
if (idom[u] != sdom[u]) idom[u] = idom[idom[u]];
}
/*
此刻现在所有 idom[u] 已经求出，即可建支配树
*/
}
int main () {
n = read(), m = read();
for (register int i = 1, u, v; i <= m; i ++)
u = read(), v = read(), Add (0, u, v), Add (1, v, u);
Build (1);
return 0;
}