【学习笔记】支配树

学习笔记, 支配树

不想复读了。

（注意上面博客中的大小比较都是基于 $dfn$ 的）

求 $semi$，就根据 $semi$ 性质中最后一条来，由于 $semi \leq$ 「所有祖先链上的最小 $semi$」，用带权并查集维护这个东西。还是很直观的。

求 $idom$，先把 $idom(x) = semi(x)$ 的确定下来，剩下的记录 $x$ 同哪个 $t$ 相同，最后正推一遍即可。

luogu 模板：

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
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define per(i, x, y) for (int i = x; i >= y; i--)
#define pb push_back
using namespace std;

const int N = 1e6 + 10;
int n, m, num[N];
vector<int> g[N], rg[N], buc[N];

namespace dominater {
    int dfn[N], clk, rdfn[N], fa[N];
    int semi[N], idom[N], best[N], c[N];  // best 是带权并查集上维护链最小 semi 位置的

    void init() {
        clk = 0;
        rep(i, 0, n + 1) {
            c[i] = -1;
            buc[i].clear();
            semi[i] = best[i] = i;  // 初始化先设为自己
            dfn[i] = 0;
        }
    }
    void dfs(int x) {
        dfn[x] = ++clk, rdfn[clk] = x;
        for (int i = 0; i < g[x].size(); i++) {
            int y = g[x][i]; if (!dfn[y]) fa[y] = x, dfs(y);
        }
    }
    int fix(int x) {
        if (c[x] == -1) return x;
        int &f = c[x], t = fix(f);
        if (dfn[semi[best[x]]] > dfn[semi[best[f]]]) best[x] = best[f];
        return f = t;
    }
    void work(int rt) {
        dfs(rt);
        for (int i = clk; i; --i) {
            int x = rdfn[i], mn = clk + 1;  // mn: 祖先链上最小的 semi
            for (int j = 0; j < rg[x].size(); j++) {
                int u = rg[x][j];
                if (!dfn[u]) continue;  // 可能无法到达所有点
                fix(u);
                mn = min(mn, dfn[semi[best[u]]]);
            }
            c[x] = fa[x];
            semi[x] = rdfn[mn], buc[semi[x]].pb(x);
            x = rdfn[i - 1];

            for (int j = 0; j < buc[x].size(); j++) {
                int u = buc[x][j];
                fix(u);
                if (semi[best[u]] != x)  // 此处 best[u] 为 idom 性质第二条中的 t
                    idom[u] = best[u];  // 先指向 t，之后正推一遍得到所有 idom
                else
                    idom[u] = x;
            }
            buc[x].clear();
        }
        buc[1].clear();
        rep(i, 2, clk) {  // 正推啦
            int x = rdfn[i];
            if (idom[x] != semi[x])  // 此时的 idom[x] 是 t
                idom[x] = idom[idom[x]];
            buc[idom[x]].pb(x);
        }
    }
};
using namespace dominater;

int main() {
    scanf("%d%d", &n, &m);
    init();
    rep(i, 1, m) {
        int x, y; scanf("%d%d", &x, &y);
        g[x].pb(y), rg[y].pb(x);
    }
    work(1);

    per(i, clk, 1) {
        int x = rdfn[i];
        num[x] = 1;
        for (int j = 0; j < buc[x].size(); j++) {
            num[x] += num[buc[x][j]];
        }
    }
    rep(i, 1, n) printf("%d ", num[i]); puts("");
    return 0;
}