定义
对于一张有向图，确定一个根，如果根到 $x$ 的每条路径都经过 $y$，那么称 $y$ 是 $x$ 的支配点。求出原图的一个 dfs 树，那么 $x$ 的支配点一定在 $x$ 到根的链上。如果每个点向自己深度最大的支配点（记作 $\text{idom}(u)$）连边，就构成了支配树。
有向图 dfs 树的性质
- 图中所有两个端点没有祖先后代关系的非树边都从 dfn 大的点指向 dfn 小的点。
- 若 u 和 v 满足 u 的 dfn 比 v 的 dfn 小，那么图中任意从 u 到 v 的路径一定包含至少一个 u 和 v 的公共祖先。
算法流程
初步分析
对于 DAG，可以直接 LCA 做，复杂度 $O(n \log n)$。下面介绍对于所有图适用的算法：Lengauer Tarjan 算法，它的时间复杂度是 $O(n\cdot\alpha(n))$。
如果 $y$ 不是 $x$ 的后代，且满足存在 $y$ 到 $x$ 的一条路径，使得路径上的点（除 $x, y$）dfn 都大于 $\text{dfn}(x)$，那么称 $y$ 是 $x$ 的一个半支配点。可以证明 $x$ 的半支配点一定是 $x$ 的祖先，我们记 $\text{sdom}(x)$ 为 $x$ 半支配点中深度最小的点。
我们考虑先求出 $\text{sdom}$ 后再求出 $\text{idom}$。
求半支配点
考虑枚举路径上 $x$ 之前的那个点 $y$（满足 $\text{dfn}(y) > \text{dfn}(x)$）。$x$ 的半支配点是某个 $z$ 点的半支配点，其中 $z$ 是 $y$ 的祖先且 $\text{dfn}(z) > \text{dfn}(x)$。我们要求的就是 $z$ 点的最小值。考虑把所有点按照 $\text{dfn}(x)$ 从大到小排序，一一加入一个维护树结构的并查集，并查集中的每个点维护它到当前根的最小值即可。
求支配点
对于某点 $x$，记 $P_x$ 表示对于 $x$ 祖先链上的每个 $y$，树上路径 $\text{semi}(y) \rightarrow y$ 的并集。找到 $P_x$ 中深度最小的点 $z$，则：
- semi(x) = semi(z) 时，idom(x) = semi(x)；
- 否则，idom(x) = idom(z)。
类似地，将点按照 $\text{semi}(x)$ 的深度从大到小排序，使用带权并查集维护即可。
代码实现
1 | // Luogu P5180 支配树模版 |
2 | |
3 | using namespace std; |
4 | |
5 | namespace __main__ { |
6 | const int maxn = 2e5; |
7 | int n, m, tot, dfn[maxn + 3], o[maxn + 3], dep[maxn + 3]; |
8 | int fa[maxn + 3], num[maxn + 3], lnk[maxn + 3], cnt[maxn + 3]; |
9 | int sdom[maxn + 3], idom[maxn + 3], ans[maxn + 3]; |
10 | vector<int> G[maxn + 3], T[maxn + 3], B[maxn + 3], D[maxn + 3]; |
11 | |
12 | void add(int u, int v) { |
13 | G[u].push_back(v); |
14 | B[v].push_back(u); |
15 | } |
16 | |
17 | void dfs(int u) { |
18 | dfn[u] = ++tot, o[tot] = u; |
19 | D[dep[u]].push_back(u); |
20 | for (int i = 0, v; i < G[u].size(); i++) { |
21 | v = G[u][i]; |
22 | if (dfn[v]) continue; |
23 | T[u].push_back(v); |
24 | dep[v] = dep[u] + 1; |
25 | dfs(v); |
26 | } |
27 | } |
28 | |
29 | int min_1(int a, int b) { |
30 | if (!a || !b) return a | b; |
31 | return dfn[a] < dfn[b] ? a : b; |
32 | } |
33 | |
34 | int min_2(int a, int b) { |
35 | return dfn[sdom[a]] < dfn[sdom[b]] ? a : b; |
36 | } |
37 | |
38 | int find(int x) { |
39 | if (fa[x] == x) { |
40 | return x; |
41 | } |
42 | int y = fa[x]; |
43 | fa[x] = find(y); |
44 | if (y != fa[x]) { |
45 | num[x] = min_2(num[x], num[y]); |
46 | } |
47 | return fa[x]; |
48 | } |
49 | |
50 | void main() { |
51 | scanf("%d %d", &n, &m); |
52 | for (int u, v, i = 1; i <= m; i++) { |
53 | scanf("%d %d", &u, &v); |
54 | add(u, v); |
55 | } |
56 | dep[1] = 1; |
57 | dfs(1); |
58 | for (int i = 1; i <= n; i++) { |
59 | fa[i] = i; |
60 | } |
61 | for (int i = n, u; i; i--) { |
62 | u = o[i]; |
63 | for (int j = 0, v; j < B[u].size(); j++) { |
64 | v = B[u][j]; |
65 | sdom[u] = min_1(sdom[u], v); |
66 | find(v); |
67 | sdom[u] = min_1(sdom[u], min_1(sdom[num[v]], sdom[num[fa[v]]])); |
68 | } |
69 | num[u] = u; |
70 | for (int j = 0; j < T[u].size(); j++) { |
71 | fa[T[u][j]] = u; |
72 | } |
73 | } |
74 | for (int i = 1; i <= n; i++) { |
75 | cnt[dep[sdom[i]]]++; |
76 | } |
77 | for (int i = n; i; i--) { |
78 | cnt[i] += cnt[i + 1]; |
79 | } |
80 | for (int i = 1; i <= n; i++) { |
81 | o[cnt[dep[sdom[i]]]--] = i; |
82 | } |
83 | for (int i = 1; i <= n; i++) { |
84 | fa[i] = i; |
85 | } |
86 | int p = n + 1; |
87 | for (int i = 1, u; i <= n; i++) { |
88 | u = o[i]; |
89 | while (p > dep[sdom[u]]) { |
90 | p--; |
91 | for (int j = 0, v; j < D[p].size(); j++) { |
92 | v = D[p][j], num[v] = v; |
93 | for (int k = 0; k < T[v].size(); k++) { |
94 | fa[T[v][k]] = v; |
95 | } |
96 | } |
97 | } |
98 | find(u); |
99 | if (sdom[num[u]] == sdom[u]) { |
100 | idom[u] = sdom[u]; |
101 | } else { |
102 | lnk[u] = num[u]; |
103 | } |
104 | } |
105 | idom[1] = 0; |
106 | for (int i = 1; i <= n; i++) { |
107 | for (int j = 0, u; j < D[i].size(); j++) { |
108 | u = D[i][j]; |
109 | if (!idom[u]) { |
110 | idom[u] = idom[lnk[u]]; |
111 | } |
112 | } |
113 | } |
114 | for (int i = 1; i <= n; i++) { |
115 | ans[i] = 1; |
116 | } |
117 | for (int i = n; i; i--) { |
118 | for (int j = 0, u; j < D[i].size(); j++) { |
119 | u = D[i][j]; |
120 | ans[idom[u]] += ans[u]; |
121 | } |
122 | } |
123 | for (int i = 1; i <= n; i++) { |
124 | printf("%d%c", ans[i], " \n"[i == n]); |
125 | } |
126 | } |
127 | } |
128 | |
129 | int main() { |
130 | __main__::main(); |
131 | return 0; |
132 | } |