图的连通性

2025-12-26T11:07:48+08:00 | 6分钟阅读 | 更新于 2025-12-26T11:07:48+08:00

@
图的连通性

我尝尝追忆过去。

生命瞬间定格在脑海，我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。

1. 有向图的连通性

1.1 相关定义

1.2 DFS 树

2. 无向图连通性

2.1 相关定义

2.2 DFS 树

2.3 双联通

2.4 Menger 定理

3. 耳分解与双极定向

3.1 相关定义

  • 耳：可以视作一个动态的过程，实际上是对静态图的刻画。对于图 $G$ 的子图 $G’=(V’,E’)$，若一个简单环或简单路径 $P=p_1\to p_2\to\cdots\to p_k$ 满足 $p_1,p_k\in V’$，且 $p_2,\cdots,p_{k-1}\not\in V’$，则称 $P$ 为 $G$ 关于 $G’$ 的耳。特别的，$P$ 为简单路径（即 $p_1\not=p_k$）时，且满足上述关系时，称作开耳。
  • 耳分解：

4. DAG 上可达性问题

Recallllllllllllllll

P11831 [省选联考 2025] 追忆

先考虑不带修怎么做。

对 $a$ 值域分块，设 $f_{i,x}$ 表示 $i$ 点可到达的范围在第 $x$ 个块内的所有点的 $b$ 的最大值。对每个点用 bitset 维护所有可达的 $b$，复杂度 $\mathcal O(\dfrac{B_1m}\omega\times \dfrac n{B_1})=\mathcal O(\dfrac{nm}{\omega})$，注意这里 $\omega$ 的取值。查询时直接 $\mathcal O(\sqrt n)$ 查就行了。

下面考虑带修怎么做。

一个很经典的方法就是操作分块，也就是每 $B_2$ 个操作后重构。对于块内查询操作，判断交换后的 $\mathcal O(B_2)$ 个点 chkmax 即可。总复杂度为 $\mathcal O(\dfrac{nmq}{B_1B_2}+q(B_1+B_2+\dfrac{n}{B_1}))$，$B_1=B_2=n^{\frac 2/3}$ 时最优。

  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

const int N = 1e5 + 10;
const int B = 3500;
const int L = N / B + 10;

int n, m, q;
int a[N], b[N], cors[N];
int f[L][N], cnnt, id[N], LLL[N], RRR[N];
bool used[N];
vector <int> g[N];
bitset <N> reach[N];

void init () {
    for (int i = 1; i <= cnnt; i ++) {
        LLL[i] = RRR[i - 1] + 1;
        RRR[i] = min (n, LLL[i] + B - 1);
        for (int j = LLL[i]; j <= RRR[i]; j ++) id[j] = i;
    }
}

void upd (int block) {
    int l = LLL[block], r = RRR[block];
    for (int i = 1; i <= n; i ++) f[block][i] = 0; 
    for (int i = n; i; i --) {
        if (a[i] >= l && a[i] <= r && !used[i]) chkmax (f[block][i], b[i]);
        for (const auto& v : g[i])  chkmax (f[block][i], f[block][v]);
    }
}

void prework () {
    for (int i = n; i; i --) {
        reach[i][i] = true;
        for (const auto& v : g[i]) reach[i] |= reach[v];
    }
    cnnt = (n + B - 1) / B;
    init ();
}

int usdp[N], Cnt, sta, stb;
void push (int x) {
    if (!used[x]) {
        used[x] = true;
        usdp[++ Cnt] = x;
    }
}

int query (int x, int l, int r, auto& ca, auto& cb, int tim) {
    for (; sta < ca.size ();) {
        auto [x, y, t] = ca[sta];
        if (t > tim) break; 
        swap (a[x], a[y]), cors[a[x]] = x, cors[a[y]] = y;
        sta ++;
    }
    for (; stb < cb.size ();) {
        auto [x, y, t] = cb[stb];
        if (t > tim) break; 
        swap (b[x], b[y]);
        stb ++;
    }

    int ans = 0, L = id[l], R = id[r];
    auto getinfo = [&](int L, int R) {
        for (int i = L; i <= R; i ++) 
            if (reach[x][cors[i]]) chkmax (ans, b[ cors[i] ]);
    };  
    if (L == R) getinfo (l, r);
    else {
        getinfo (l, RRR[L]);
        for (int i = L + 1; i < R; i ++) chkmax (ans, f[i][x]);
        getinfo (LLL[R], r);
    } 
    for (int i = 1; i <= Cnt; i ++) if (reach[x][ usdp[i] ] && a[usdp[i]] >= l && a[usdp[i]] <= r) chkmax (ans, b[ usdp[i] ]);
    return ans;
}

void solve (auto& ca, auto& cb, auto& qry) {
    for (auto& [x, y, t] : ca) push (x), push (y);
    for (auto& [x, y, t] : cb) push (x), push (y);
    for (int i = 1; i <= cnnt; i ++) upd (i);
    for (const auto& [x, l, r, i] : qry) printf ("%d\n", query (x, l, r, ca, cb, i));
    for (; sta < ca.size (); sta ++) {auto [x, y, t] = ca[sta]; swap (a[x], a[y]), cors[a[x]] = x, cors[a[y]] = y;}
    for (; stb < cb.size (); stb ++) {auto [x, y, t] = cb[stb]; swap (b[x], b[y]);}
    sta = stb = 0;
    Cnt = 0;
    for (auto& [x, y, t] : ca) used[x] = used[y] = false;
    for (auto& [x, y, t] : cb) used[x] = used[y] = false;    
    ca.clear (), cb.clear (), qry.clear ();
}

void work () {
    for (int i = 1; i <= n; i ++) g[i].clear (), reach[i].reset ();

    scanf ("%d%d%d", &n, &m, &q);
    for (int i = 1, u, v; i <= m; i ++) scanf ("%d%d", &u, &v), g[u].push_back (v);
    for (int i = 1; i <= n; i ++) scanf ("%d", &a[i]), cors[a[i]] = i;
    for (int i = 1; i <= n; i ++) scanf ("%d", &b[i]);
    prework ();
    int cnt = 0;
    vector < tuple <int, int, int> > a, b; 
    vector < tuple <int, int, int, int> > qry;
    for (int i = 1; i <= q; i ++) {
        int opt, x, l, r;
        scanf ("%d%d%d", &opt, &x, &l);
        if (opt == 1) a.emplace_back (x, l, i);
        if (opt == 2) b.emplace_back (x, l, i);
        if (opt == 3) scanf ("%d", &r), qry.emplace_back (x, l, r, i);
        if ((++ cnt) == B) solve (a, b, qry), cnt = 0;
    }
    if (cnt) solve (a, b, qry), cnt = 0;
}

洛谷能过。loj 最后三个点差了十几毫秒/ll。

给出 $n$ 个点的无根树，边有长度。每个点有爆炸半径 $r_i$，引爆某个点会导致树上距离 $\le r_i$ 的点爆炸，进而爆炸其他点。对于所有点，求引爆后爆炸的点的总数。

$n\le 10^5$。

P9260 [PA 2022] Miny

序列版本是 P5025 。

假设 $u$ 可以引爆 $v$，设 $dis_u$ 为 $u$ 到二者 LCA 的距离，需要满足 $dis_u+dis_v\le r_u$，即 $dis_v\le r_u-dis_u$。假设已经确定所有的 $(u,v)$ 对，那么可以用双指针维护，进而用前缀优化建图来做这个事。

注意到点分治的结构，递归层数是 $\mathcal O(\log n)$ 的，于是考虑点分治。分别对 $r_u-dis_u$ 以及 $dis_u$ 排序，双指针维护即可。另外，对于 LCA 不是当前分治中心的两点，被提前统计仍然可行，因为这是一个更为严格的限制。这样就建出了 $\mathcal O(n\log n)$ 级别的图。

接下来考虑统计，首先将图缩点成 DAG。接下来就是 DAG 上可达性问题，即统计所有点可到达的点的数量，取 DAG 的反图。朴素的 bitset 难以接受，可以将 bitset 分块处理。或者使用主席树合并的方法来做。图的度数在 $\mathcal O(n\log n)$ 级别。这里采用主席树而非普通线段树合并的原因是，如果一个点同时指向多个点，在修改某一指向点时可能会同时修改到当前点，进而导致答案出错。

下面的代码是主席树合并实现的，主席树合并的空间复杂度取决于每次合并相同结构的数量，加上集合 hash 判重可能有奇效。但在精心构造的图下会存不下，见 LOJ 数据，懒得写 bitset 分块了。

  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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167

#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>

#define mp make_pair
using ll = long long;

using namespace std;

const int N = 1e5 + 10; 
const int NN = 4e6 + 10;

int n;
ll r[N];
vector < pair <int, ll> > tr[N];
vector <int> g[NN], ng[NN], colu[NN];
int fa[N], sz[N], used[N], G, weight = 1e9, tot;
ll dis[N];
vector < pair <ll, int> > t1, t2;

void link (int u, int v) {
    g[u].push_back (v);
}

void dfs (int u, int fr) {
    sz[u] = 1;
    for (auto& [v, c] : tr[u]) {
        if (v == fr || used[v]) continue;
        dis[v] = dis[u] + c;
        dfs (v, u);
        sz[u] += sz[v];
    }
}

void getG (int u, int fr, int rt) {
    int mxson = 0;
    for (auto& [v, c] : tr[u]) {
        if (v == fr || used[v]) continue;
        getG (v, u, rt);
        mxson = max (mxson, sz[v]);
    }
    int now = max (mxson, sz[rt] - sz[u]);
    if (weight > now) G = u, weight = now; 
}

void getval (int u, int fr) {
    t1.emplace_back (r[u] - dis[u], u);
    t2.emplace_back (dis[u], u);
    for (const auto& [v, w] : tr[u]) {
        if (used[v] || fr == v) continue;
        getval (v, u);
    }
}

void divide (int root) {
    dis[root] = 0;
    dfs (root, 0);
    getval (root, 0); 

    sort (t1.begin (), t1.end ()); sort (t2.begin (), t2.end ());
    if (t1.empty ()) return ;
    int j = 0; bool flag = false;
    for (int i = 0; i < t1.size (); i ++) {
        if (i && t1[i] == t1[i - 1]) { link (t1[i].second, tot); continue; }
        ++ tot;
        if (flag) link (tot, tot - 1);
        flag = true;
        while (j < t2.size () && t1[i].first >= t2[j].first) link (tot, t2[j ++].second);
        link (t1[i].second, tot);
    } 

    t1.clear (), t2.clear ();
    used[root] = true;
    for (const auto& [v, c] : tr[root]) {
        if (used[v]) continue;
        weight = 1e9;
        getG (v, root, v);
        divide (G);
    } 
}

int dfn[NN], low[NN], tim;
int stk[NN], tp, col[NN], colid;
bool inst[NN];

void tarjan (int u) {
    inst[u] = true; stk[++ tp] = u;
    dfn[u] = low[u] = ++ tim;
    for (const auto& v : g[u])
        if (!dfn[v]) tarjan (v), low[u] = min (low[u], low[v]);
        else if (inst[v]) low[u] = min (low[u], dfn[v]);
    if (dfn[u] == low[u]) {
        ++ colid;
        do {
            colu[colid].push_back (stk[tp]);
            col[ stk[tp] ] = colid;
            inst[ stk[tp] ] = false; 
        } while (stk[tp --] != u);
    }
}

// 点分治建图

int deg[NN];
int rt[NN * 25], ls[NN * 25], rs[NN * 25], t[NN * 25], cnt, ans[NN];

#define mid (l + r >> 1)

void insert (int& u, int p, int l = 1, int r = n) {
    if (!u) u = ++ cnt;
    t[u] ++;
    if (l == r) return ;
    if (p <= mid) insert (ls[u], p, l, mid);
    else          insert (rs[u], p, mid + 1, r);
}

int merge (int u, int v, int l = 1, int r = n) {
    if (!u || !v) return u | v; 
    if (l == r) return u;
    int p = ++ cnt;
    ls[p] = merge (ls[u], ls[v], l, mid);
    rs[p] = merge (rs[u], rs[v], mid + 1, r);
    t[p] = t[ls[p]] + t[rs[p]];
    return p;
} // 主席树合并

int main (void) {

    scanf ("%d", &n); tot = n;
    for (int i = 1; i <= n; i ++) scanf ("%lld", r + i);
    for (int i = 1; i < n; i ++) {
        int u, v; ll c; scanf ("%d%d%lld", &u, &v, &c);
        tr[u].emplace_back (v, c), tr[v].emplace_back (u, c);
    }
    dfs (1, 0); getG (1, 0, 1);
    divide (G);

    for (int i = 1; i <= tot; i ++) if (!dfn[i]) tarjan (i);
    for (int i = 1; i <= tot; i ++) 
        for (const auto& v : g[i]) {
            int x = col[i], y = col[v];
            if (x != y) ng[y].push_back (x);
        }
    for (int i = 1; i <= colid; i ++) {
        sort (ng[i].begin (), ng[i].end ());
        ng[i].erase (unique (ng[i].begin (), ng[i].end ()), ng[i].end ());
        for (auto& v : ng[i]) ++ deg[v];
    }
    
    queue <int> q;
    for (int i = 1; i <= colid; i ++) if (!deg[i]) q.push (i);
    for (int i = 1; i <= colid; i ++) for (const auto& u : colu[i]) if (u <= n) insert (rt[i], u);
    while (!q.empty ()) {
        int u = q.front (); q.pop ();
        ans[u] = t[rt[u]];
        for (const auto& v : ng[u]) {
            rt[v] = merge (rt[v], rt[u]);
            if (!-- deg[v]) q.push (v);
        }
    }

    for (int i = 1; i <= n; i ++) printf ("%d ", ans[col[i]]);
    puts ("");

    return 0;
}

© 2025 - 2026 Toorean's Blog

🌱 Powered by Hugo with theme Dream.

About Me

来自安徽合肥，目前在合肥市第一中学读高中。

弱小的 OIer，或许就要退役了呢？

QQ: 3427463298 Email: phantomxbee@outlook.com