[模板] 支配树

支配树的算法很妙。它的证明实在太长了….完整写一遍比较费时间,这里就只写结论了。

显然支配关系构成一棵树。

定义 \(sdom(u)\) 是能够从 \(v\) 出发只经过 \(dfn\)\(u\) 大的到达 \(u\)\(u\)\(v\) 不算在里面)的 \(dfn\) 最小的 \(v\)

\(sdom(u)\) 要么是能够通过一条前向边 / 树边直接到达 \(u\) 的点,要么是满足子树中存在至少一个点能够直接走到 \(u\)\(dfn\)\(u\) 大的点的 \(sdom\)。根据这一点可以并查集计算 \(sdom\)。并查集维护的是链 sdom 的最小值。

\(v\)\(u\)\(sdom(u)\) 的链上(不含 \(sdom(u)\)\(sdom\) 最小的点 ,那么如果 \(sdom(v) = sdom(u)\)\(idom(u) = sdom(u)\),否则 \(idom(u) = idom(v)\)。这个东西也是要求一个链 sdom 的最小值。可以求 \(sdom\) 的时候顺便维护一下。

在这份代码中 \(sdom\) 存的是 \(dfn\) 最小的点的 \(dfn\) 而不是编号,需要特别注意。

(听说这题数据很水…说不定有错没被查出来)

这份代码被提交到 【模板】支配树

代码

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
#include <bits/stdc++.h>

using namespace std;

const int maxn = 200010;
const int maxm = 300010;

int n, m, tot;
int l[maxn], dfn[maxn], vis[maxn], a[maxn], sdom[maxn], idom[maxn], e;
int fa[maxn], mn[maxn], mnp[maxn], sz[maxn];
vector<int> vec[maxn], b[maxn], son[maxn], tree[maxn];

struct Edge {
int v, x;
} E[maxm];

inline void addEdge(int u, int v) {
E[e].v = v; E[e].x = l[u]; l[u] = e++;
}

void dfs(int u) {
dfn[u] = ++ tot; a[tot] = u; vis[u] = 1;
for (int p = l[u]; p >= 0; p = E[p].x) {
int v = E[p].v;
if (!dfn[v]) {
sdom[v] = min(sdom[v], dfn[u]);
son[u].push_back(v);
dfs(v);
} else if (!vis[v] && dfn[u] < dfn[v]) {
sdom[v] = min(sdom[v], dfn[u]);
}
if (dfn[u] > dfn[v]) vec[v].push_back(u);
}
vis[u] = 0;
}

int Min(int x, int y) {
return sdom[x] < sdom[y] ? x : y;
}

int getroot(int x) {
if (x == fa[x]) return x;
int f = getroot(fa[x]);
mn[x] = Min(mn[x], mn[fa[x]]);
fa[x] = f;
return f;
}

void calsize(int u) {
sz[u] = 1;
for (int i = 0; i < tree[u].size(); i++) {
int v = tree[u][i];
calsize(v);
sz[u] += sz[v];
}
}

int main() {
memset(l, -1, sizeof(l));
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
addEdge(u, v);
}
for (int i = 1; i <= n; i++) sdom[i] = n+1;
dfs(1);
for (int i = 1; i <= n; i++) fa[i] = i, mn[i] = i;
for (int _ = n; _ >= 1; _--) {
int i = a[_];
for (int j = 0; j < vec[i].size(); j++) {
int u = vec[i][j]; getroot(u);
sdom[i] = min(sdom[i], sdom[mn[u]]);
}
b[a[sdom[i]]].push_back(i);
for (int j = 0; j < b[i].size(); j++) {
int u = b[i][j];
getroot(u);
mnp[u] = mn[u];
}
for (int j = 0; j < son[i].size(); j++) {
int u = son[i][j];
fa[u] = i;
}
}
for (int _ = 2; _ <= n; _++) {
int i = a[_];
if (sdom[mnp[i]] < sdom[i]) idom[i] = idom[mnp[i]];
else idom[i] = a[sdom[i]];
}
for (int i = 2; i <= n; i++) tree[idom[i]].push_back(i);
calsize(1);
for (int i = 1; i <= n; i++) printf("%d ", sz[i]);
puts("");
return 0;
}