P1197 [JSOI2008] 星球大战 · 习题解析｜信息学奥赛算法练功房

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库。

转录自洛谷 P1197，日期见页头。两边不一致时信原站。

题目描述

很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治着整个星系。某一天，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。

但好景不长，帝国又重新造出了超级武器，开始有计划地摧毁反抗军占领的星球。

现在，反抗军首领交给你一个任务：给出原来两个星球之间的以太隧道连通情况以及帝国打击的星球顺序，以尽量快的速度求出每一次打击之后反抗军占据的星球的连通块的个数。

输入格式

第一行包含两个整数 n, m，分别表示星球的数目和以太隧道的数目。星球用 0 ~ n−1 的整数编号。

接下来的 m 行，每行包括两个整数 x, y，表示星球 x 和星球 y 之间有「以太」隧道。

接下来的一行为一个整数 k，表示将遭受攻击的星球的数目。接下来的 k 行，按照顺序列出了帝国军的攻击目标。这 k 个数互不相同。

输出格式

第一行是开始时星球的连通块个数。接下来的 k 行，每行一个整数，表示经过该次打击后现存星球的连通块个数。

数据规模与约定

对于 100% 的数据，1 ≤ m ≤ 2 × 10⁵，1 ≤ n ≤ 2m，x ≠ y。

时限 1 秒，内存 128 MB。

输入输出样例

输入

输出

⚠ 输出是 k + 1 行（第一行是「一次都还没打」时的连通块数）—— 第 ④ 步专门讲它。

1★★ 关键的一步：并查集拆不开，那就把时间倒过来

p1197.cpp★ 这一版就能 AC（顶格 n = m = 2×10⁵ / k = n/2，本机 16 毫秒）

// P1197 [JSOI2008] 星球大战 —— ★ 这一版就能 AC
//
// ★★ 关键的一步只有一句话：**并查集只能合并、不能拆开**（这一章那片森林的必然结果）
//   ⇒ 所以把时间**倒过来**：
//     ① 先把 k 个要被摧毁的星球**全部**摧毁，对剩下的图算一次连通块数 —— 那是**最后一行**答案；
//     ② 然后倒着一个个**恢复**：恢复 x 时先 cnt++（它自己算一块），
//        再看它的每条边，另一端**已经恢复**且不同块 ⇒ 合并、cnt--。
//     ③ 把答案倒着打出来。
//
// ⚠ 输出是 **k + 1 行**：第一行是「一次都还没打」时的连通块数（本页第 ④ 步）。
// ⚠ 星球编号是 **0 ~ n−1**（不是 1 ~ n）。
#include <bits/stdc++.h>
using namespace std;

static const int N = 400005;
static int fa[N];
static bool dead[N];

static int find(int x) {
    int r = x;
    while (fa[r] != r) r = fa[r];
    while (fa[x] != r) { int nx = fa[x]; fa[x] = r; x = nx; }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<pair<int, int>> es(m);
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        es[i] = {x, y};
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int k;
    cin >> k;
    vector<int> hit(k);
    for (int i = 0; i < k; i++) { cin >> hit[i]; dead[hit[i]] = true; }

    for (int i = 0; i < n; i++) fa[i] = i;
    int cnt = n - k;                                  // 活着的星球，每个先算一块
    for (auto& e : es) {
        if (dead[e.first] || dead[e.second]) continue;
        int a = find(e.first), b = find(e.second);
        if (a != b) { fa[a] = b; cnt--; }
    }

    vector<int> ans(k + 1);
    ans[k] = cnt;                                     // ★ 全部打完之后的那一行
    for (int i = k - 1; i >= 0; i--) {
        int x = hit[i];
        dead[x] = false;
        cnt++;                                        // 它自己先算一块
        for (int y : g[x]) {
            if (dead[y]) continue;                    // ⚠ 另一端还没恢复，这条边不算
            int a = find(x), b = find(y);
            if (a != b) { fa[a] = b; cnt--; }
        }
        ans[i] = cnt;
    }
    string out;
    for (int i = 0; i <= k; i++) { out += to_string(ans[i]); out += '\n'; }
    cout << out;
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★ 「只能合并、不能拆」不是缺陷，是这一章那片森林的必然结果

本章整章都在讲那两句话（路径压缩＋按秩合并）—— 而它们干的事都是把树压扁、把两棵树接起来。一旦压扁了，「谁本来挂在谁下面」这件事就永远找不回来了 ⇒ 拆不开。

⇒ 于是这道题的做法只有一句话：倒着做。

① 先把 k 个要被摧毁的星球全部摧毁，对剩下的图算一次连通块数 —— 那是**最后一行**答案
② 倒着一个个恢复：恢复 x 时 cnt++（它自己算一块），
   再看它的每条边，另一端**已经恢复**且不同块 ⇒ 合并、cnt--
③ 把答案倒着打出来

★ 「删点」是并查集做不到的操作，「加点」是它天生就会的 —— 把时间翻过来，删就变成了加。

2⚠ 三个错法，官方样例全挡住了

p1197Dead.cpp✗ 初始连通块数算成 n（样例每一行都大 5）

// P1197 · 错法 ①：初始连通块数算成了 n
//
// ⚠ 一开始已经有 k 个星球被摧毁了，它们**不算连通块** ⇒ 起点是 `n − k`，不是 `n`。
// ★ 它的答案恒**比正解大 k**（每一行都大 k）—— 是那种「说得清算了什么」的 bug。
#include <bits/stdc++.h>
using namespace std;

static const int N = 400005;
static int fa[N];
static bool dead[N];

static int find(int x) {
    int r = x;
    while (fa[r] != r) r = fa[r];
    while (fa[x] != r) { int nx = fa[x]; fa[x] = r; x = nx; }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<pair<int, int>> es(m);
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        es[i] = {x, y};
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int k;
    cin >> k;
    vector<int> hit(k);
    for (int i = 0; i < k; i++) { cin >> hit[i]; dead[hit[i]] = true; }

    for (int i = 0; i < n; i++) fa[i] = i;
    int cnt = n;                                      // ✗ 把已经被摧毁的也算进去了
    for (auto& e : es) {
        if (dead[e.first] || dead[e.second]) continue;
        int a = find(e.first), b = find(e.second);
        if (a != b) { fa[a] = b; cnt--; }
    }

    vector<int> ans(k + 1);
    ans[k] = cnt;                                     // ★ 全部打完之后的那一行
    for (int i = k - 1; i >= 0; i--) {
        int x = hit[i];
        dead[x] = false;
        cnt++;                                        // 它自己先算一块
        for (int y : g[x]) {
            if (dead[y]) continue;                    // ⚠ 另一端还没恢复，这条边不算
            int a = find(x), b = find(y);
            if (a != b) { fa[a] = b; cnt--; }
        }
        ans[i] = cnt;
    }
    string out;
    for (int i = 0; i <= k; i++) { out += to_string(ans[i]); out += '\n'; }
    cout << out;
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

p1197NoCheck.cpp✗ 恢复时没检查另一端是否也已恢复（样例打出 1 0 -1 -1 1 3）

// P1197 · 错法 ②：恢复某个星球时，没检查另一端是不是也已经恢复
//
// ⚠ 倒着恢复的时候，`x` 的邻居里有一部分**还处在「已被摧毁」的状态** ——
//   那条边这一刻还不存在，不能拿来合并。
// ★ 它会把还没恢复的星球提前并进来 ⇒ 连通块数偏小。
#include <bits/stdc++.h>
using namespace std;

static const int N = 400005;
static int fa[N];
static bool dead[N];

static int find(int x) {
    int r = x;
    while (fa[r] != r) r = fa[r];
    while (fa[x] != r) { int nx = fa[x]; fa[x] = r; x = nx; }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<pair<int, int>> es(m);
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        es[i] = {x, y};
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int k;
    cin >> k;
    vector<int> hit(k);
    for (int i = 0; i < k; i++) { cin >> hit[i]; dead[hit[i]] = true; }

    for (int i = 0; i < n; i++) fa[i] = i;
    int cnt = n - k;                                  // 活着的星球，每个先算一块
    for (auto& e : es) {
        if (dead[e.first] || dead[e.second]) continue;
        int a = find(e.first), b = find(e.second);
        if (a != b) { fa[a] = b; cnt--; }
    }

    vector<int> ans(k + 1);
    ans[k] = cnt;                                     // ★ 全部打完之后的那一行
    for (int i = k - 1; i >= 0; i--) {
        int x = hit[i];
        dead[x] = false;
        cnt++;                                        // 它自己先算一块
        for (int y : g[x]) {
            // ✗ 少了 if (dead[y]) continue; ——— 另一端还没恢复也照并
            int a = find(x), b = find(y);
            if (a != b) { fa[a] = b; cnt--; }
        }
        ans[i] = cnt;
    }
    string out;
    for (int i = 0; i <= k; i++) { out += to_string(ans[i]); out += '\n'; }
    cout << out;
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

p1197Rows.cpp✗ 只输出 k 行（漏掉第一行）

★ 而「初始算成 n」漏掉的那些轮，能数到底

300 轮	档 0	★★ 档 1 `k = 0`	档 2 全部打光	档 3 图是一棵树
`k == 0` 的轮数	★ 0	300	★ 0	★ 0
⇒ 「初始算成 n」漏掉的轮数	★ 0	300	★ 0	★ 0

★★ 四个档一个不差 —— 一行就能证：初始 cnt 写成 n 而不是 n − k，两版永远差正好 k；k = 0 时那个差就是 0。 ⚠ 而「恢复时不判另一端」只在 k = 0 那一档上和它对得上（那一档压根没有恢复步骤）—— 别的档它漏得多得多（155 / 0 / 162）：并进来的那个点不一定改变连通块数。

3★★ 而这道题最值钱的一条：有一个「答案永远对」的写法，对拍和样例都是聋的

p1197Forward.cpp⚠ 正着做：每摧毁一个就重数一遍连通块 —— 答案永远对，顶格 8 × 10¹⁰ 次

// P1197 · 另一条**正确**的路：正着做 —— 每摧毁一个星球，就把整张图重新数一遍连通块
//
// ★ 它一个技巧都不用，答案永远对 —— 拿它当对拍的参照物正合适。
// ⚠ 而复杂度是 O(k × (n + m))：顶格 2×10⁵ × 4×10⁵ = **8 × 10¹⁰**，一秒钟连零头都跑不完。
//   ⇒ 又一次「答案对但跑不完」—— **对拍和官方样例对这种 bug 都是聋的**（本页第 ③ 步）。
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int k;
    cin >> k;
    vector<int> hit(k);
    for (int i = 0; i < k; i++) cin >> hit[i];
    vector<char> dead(n, 0);

    string out;
    for (int step = 0; step <= k; step++) {
        if (step > 0) dead[hit[step - 1]] = 1;
        vector<char> vis(n, 0);
        int cnt = 0;
        for (int s = 0; s < n; s++) {
            if (dead[s] || vis[s]) continue;
            cnt++;
            vector<int> q{s};
            vis[s] = 1;
            for (size_t h = 0; h < q.size(); h++) {
                int u = q[h];
                for (int v : g[u]) if (!dead[v] && !vis[v]) { vis[v] = 1; q.push_back(v); }
            }
        }
        out += to_string(cnt);
        out += '\n';
    }
    cout << out;
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★★ 它 1200 轮一次都没被抓到 —— 因为它根本没错

「正着做」一个技巧都不用：每打掉一个星球，就把整张图重新 BFS 一遍数连通块。 四个档 1200 轮，和正解逐字节相同。

⚠ 而它的复杂度是 O(k × (n + m))：


题面顶格 `k × (n + m)`	★ 4 × 10¹⁰
时限	1 秒

⇒ 这是「答案对但跑不完」在这一章的现场： 对拍是聋的，官方样例也是聋的 —— 只能数次数。

「正着做」碰了多少个点（`n = m`，`k = n/2`）
`n = 2000`	1 501 500
`n = 4000`	6 003 000 ⇒ ★ ×4.00
`n = 8000`	24 006 000 ⇒ ★ ×4.00

★★ n 翻一倍，次数正好翻四倍 —— 干干净净的 O(n²) 签名（P5019 那把尺子）。 ⇒ 而倒着做那一版在顶格上只用 16 毫秒。

4⚠ 和算法无关的一条：输出是 k + 1 行

题面第一句就写着「第一行是开始时星球的连通块个数」。漏掉它，四个档全是 300 / 300。 ★ 又一次「样例是个『一测就死』的过滤器」：它挡住的三个全是「每组都错」型。

5★ 对拍这一页

参照物就是「正着做」那一版（第 ③ 步）——它慢，但小数据上快得很，而且一个技巧都不用。

300 轮（`n` 随机 5~10）	档 0	★★ 档 1 `k = 0`	★ 档 2 全部打光	★ 档 3 图是一棵树
倒着做（正解）	★ 0	★ 0	★ 0	★ 0
初始连通块算成 n	300	★ 0	300	300
恢复时不判另一端	145	★ 0	300	138
只输出 k 行	300	300	300	300

⚠⚠ 而这张表最初有一版是假的 —— 写这一页时当场踩的

第一版的生成器里，m 随机取 5~~12 而 n 只有 5~~10 —— n = 5 时最多只有 5 × 4 / 2 = 10 条不重复的边，于是那个「随机挑一对没用过的点」的 while 死循环了。

⚠ 而对拍看到的是什么？所有版本都没有输出 ⇒ 四张表全是 0 / 0 / 0 / 0，看起来「全绿」。

⇒ ★★★ 这是「一致有两种：都算对了，和都没算」的第四种：前三种是「都算对了」「都退化成常量」「轮数本身是假的」，这一次是 生成器根本没产出数据。 ⇒ ★★ 看到一整张表全是 0，先跑一次生成器看看它到底吐了什么。 ★ 修法一行：m = min(m, n * (n − 1) / 2);

6度量程序和生成器

p1197Count.cpp度量程序（本页所有数字都出自它）

p1197Gen.cpp（五个档位）数据生成器

7一页纸


★★ 关键的一步	并查集只能合并不能拆 ⇒ 把时间倒过来，删点就变成了加点
★★★ 一个「答案永远对」的写法	正着做每次重数：1200 轮 0 次不一致，而顶格 `k(n+m)` = 4 × 10¹⁰
⇒ 只能数次数	`n` 翻倍、次数正好 ×4.00（1 501 500 → 6 003 000 → 24 006 000）
★ 初始连通块	是 `n − k` 不是 `n`；两版永远差正好 k ⇒ `k = 0` 的轮数 ≡ 它漏掉的轮数（四档全中）
⚠ 输出行数	`k + 1` 行，第一行是「一次都还没打」时的 —— 四档全是 300 / 300
⚠⚠ 作者当场踩的	生成器 `m` 可能超过 `n(n−1)/2` ⇒ 死循环 ⇒ 对拍全 0 看起来全绿
⇒ 一条能带走的	看到一整张表全是 0，先跑一次生成器看看它吐了什么

洛谷 P1197 [JSOI2008] 星球大战

0题目原文（本地存了一份）

输入

输出

1★★ 关键的一步：并查集拆不开，那就把时间倒过来

2⚠ 三个错法，官方样例全挡住了

3★★ 而这道题最值钱的一条：有一个「答案永远对」的写法，对拍和样例都是聋的

4⚠ 和算法无关的一条：输出是 k + 1 行

5★ 对拍这一页

6度量程序和生成器

7一页纸