🦄️🦄️ Horse Power! ️🦄️🦄️

0%

「学习笔记」支配树与 Lengauer Tarjan 算法

发表于 Valine：

定义

对于一张有向图，确定一个根，如果根到 $x$ 的每条路径都经过 $y$，那么称 $y$ 是 $x$ 的支配点。求出原图的一个 dfs 树，那么 $x$ 的支配点一定在 $x$ 到根的链上。如果每个点向自己深度最大的支配点（记作 $\text{idom}(u)$）连边，就构成了支配树。

有向图 dfs 树的性质

  1. 图中所有两个端点没有祖先后代关系的非树边都从 dfn 大的点指向 dfn 小的点。
  2. 若 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
// Luogu P5180 支配树模版
#include <bits/stdc++.h>
using namespace std;

namespace __main__ {
	const int maxn = 2e5;
	int n, m, tot, dfn[maxn + 3], o[maxn + 3], dep[maxn + 3];
	int fa[maxn + 3], num[maxn + 3], lnk[maxn + 3], cnt[maxn + 3];
	int sdom[maxn + 3], idom[maxn + 3], ans[maxn + 3];
	vector<int> G[maxn + 3], T[maxn + 3], B[maxn + 3], D[maxn + 3];

	void add(int u, int v) {
		G[u].push_back(v);
		B[v].push_back(u);
	}

	void dfs(int u) {
		dfn[u] = ++tot, o[tot] = u;
		D[dep[u]].push_back(u);
		for (int i = 0, v; i < G[u].size(); i++) {
			v = G[u][i];
			if (dfn[v]) continue;
			T[u].push_back(v);
			dep[v] = dep[u] + 1;
			dfs(v);
		}
	}

	int min_1(int a, int b) {
		if (!a || !b) return a | b;
		return dfn[a] < dfn[b] ? a : b;
	}

	int min_2(int a, int b) {
		return dfn[sdom[a]] < dfn[sdom[b]] ? a : b;
	}

	int find(int x) {
		if (fa[x] == x) {
			return x;
		}
		int y = fa[x];
		fa[x] = find(y);
		if (y != fa[x]) {
			num[x] = min_2(num[x], num[y]);
		}
		return fa[x];
	}

	void main() {
		scanf("%d %d", &n, &m);
		for (int u, v, i = 1; i <= m; i++) {
			scanf("%d %d", &u, &v);
			add(u, v);
		}
		dep[1] = 1;
		dfs(1);
		for (int i = 1; i <= n; i++) {
			fa[i] = i;
		}
		for (int i = n, u; i; i--) {
			u = o[i];
			for (int j = 0, v; j < B[u].size(); j++) {
				v = B[u][j];
				sdom[u] = min_1(sdom[u], v);
				find(v);
				sdom[u] = min_1(sdom[u], min_1(sdom[num[v]], sdom[num[fa[v]]]));
			}
			num[u] = u;
			for (int j = 0; j < T[u].size(); j++) {
				fa[T[u][j]] = u;
			}
		}
		for (int i = 1; i <= n; i++) {
			cnt[dep[sdom[i]]]++;
		}
		for (int i = n; i; i--) {
			cnt[i] += cnt[i + 1];
		}
		for (int i = 1; i <= n; i++) {
			o[cnt[dep[sdom[i]]]--] = i;
		}
		for (int i = 1; i <= n; i++) {
			fa[i] = i;
		}
		int p = n + 1;
		for (int i = 1, u; i <= n; i++) {
			u = o[i];
			while (p > dep[sdom[u]]) {
				p--;
				for (int j = 0, v; j < D[p].size(); j++) {
					v = D[p][j], num[v] = v;
					for (int k = 0; k < T[v].size(); k++) {
						fa[T[v][k]] = v;
					}
				}
			}
			find(u);
			if (sdom[num[u]] == sdom[u]) {
				idom[u] = sdom[u];
			} else {
				lnk[u] = num[u];
			}
		}
		idom[1] = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 0, u; j < D[i].size(); j++) {
				u = D[i][j];
				if (!idom[u]) {
					idom[u] = idom[lnk[u]];
				}
			}
		}
		for (int i = 1; i <= n; i++) {
			ans[i] = 1;
		}
		for (int i = n; i; i--) {
			for (int j = 0, u; j < D[i].size(); j++) {
				u = D[i][j];
				ans[idom[u]] += ans[u];
			}
		}
		for (int i = 1; i <= n; i++) {
			printf("%d%c", ans[i], " \n"[i == n]);
		}
	}
}

int main() {
	__main__::main();
	return 0;
}

参考文献