给定一张有向图，保证 $1$ 号点可以到达所有点。求从 $1$ 号点出发，每个点能支配的点的个数 (包括自身)。
第一行包含两个正整数 $n, m$ ($n \leq 2 \times 10^5; m \leq 3 \times 10^5$)，表示点数和边数。
接下来的 $m$ 行，每行包含两个正整数 $u, v$，表示有一条从 $u$ 到 $v$ 的有向边。
输出一行，包含 $n$ 个整数，表示每个点能支配的点的个数。
题目即构造出原 (有向) 图的支配树，然后求每个点的子树大小。
支配树的相关理论可以参见便笺 "支配树及其应用"。
总时间复杂度 $O \left( n \log n \right)$ (最坏复杂度，即为路径压缩、不按秩合并的并查集复杂度)。
#include <bits/stdc++.h>
const int N = 200054, M = N * 12;
int V, E, Es = 0;
int to[M], next[M], p[N];
int first[N], inv_first[N], S_first[N];
int cnt = 0, o[N], id[N];
int S[N], I[N], ans[N];
inline void down(int &x, const int y) {x > y ? x = y : 0;}
inline void addedge(int u, int v, int *fst) {to[++Es] = v; next[Es] = fst[u]; fst[u] = Es;}
namespace U {
int p[N], w[N], st[N];
inline void init() {for (int i = 1; i <= V; ++i) w[i] = p[i] = i;}
inline void update(int &x, const int y) {id[S[x]] > id[S[y]] ? x = y : 0;}
int ancestor(int x) {
int i = 0;
for (; x != p[x]; st[++i] = x, x = p[x]);
for (st[i + 1] = x; i; p[st[i]] = x, --i) update(w[st[i]], w[st[i + 1]]);
return x;
}
inline int get_min(int x) {return ancestor(x), w[x];}
}
void dfs(int x) {
int i, y; o[++cnt] = x, id[x] = cnt;
for (i = first[x]; i; i = next[i])
if (!id[y = to[i]]) p[y] = x, dfs(y);
}
void solve() {
int i, j, x, y, r;
dfs(1), assert(cnt == V), U::init();
for (i = 1; i <= V; ++i) S[i] = i;
for (j = V; j > 1; --j) {
for (r = INT_MAX, i = inv_first[ x = o[j] ]; i; i = next[i])
y = to[i], down(r, id[ id[y] < id[x] ? y : S[U::get_min(y)] ]);
U::p[x] = p[x], S[x] = o[r], addedge(S[x], x, S_first);
for (i = S_first[ x = o[j - 1] ]; i; i = next[i])
r = U::get_min(y = to[i]), I[y] = (S[r] == x ? x : r);
}
for (; ++j <= V; ) x = o[j], I[x] != S[x] && (I[x] = I[I[x]]);
}
int main() {
int i, u, v;
scanf("%d%d", &V, &E);
for (i = 0; i < E; ++i) scanf("%d%d", &u, &v), addedge(u, v, first), addedge(v, u, inv_first);
solve();
for (i = 1; i <= V; ++i) ans[i] = 1;
for (i = V; i > 1; --i) v = o[i], ans[I[v]] += ans[v];
for (i = 1; i <= V; ++i) printf("%d%c", ans[i], i == V ? 10 : 32);
return 0;
}
坑1：注意在求半支配点的时候要满足 $id[z] > id[x]$，因此初始时要置所有点的半支配点为 $+ \infty$。
坑2：注意比较的时候使用的是 dfs 序而不是点的编号，还有就是半支配点是和生成外向树 (树形图) 有关的，不是恒定的；支配点只和有向图与起点有关，与生成树无关。