NOI 竞赛模拟题：尽量减少恶意软件的传播

题目描述

在给定的网络中，有 $n$ 个节点，节点编号为 $0$ 到 $n-1$。网络以邻接矩阵 $graph$ 的形式给出，其中 $graph[i][j] = 1$ 表示节点 $i$ 和 $j$ 之间有直接连接，否则 $graph[i][j] = 0$。

一些节点最初被恶意软件感染，记为数组 initial。当一个节点被感染后，它会通过网络连接传播到该节点所在的整个连通分量。

我们现在可以从 initial 数组中移除恰好一个节点。请注意，移除该节点意味着它最初不再被感染，但如果它仍然与被感染的节点连接，它最终仍会被感染。

请返回移除后能使最终网络中感染节点数最小的那个节点。如果有多个节点满足条件，返回索引最小的节点。

---

输入格式

第一行包含一个整数 $n$，表示节点总数。 接下来 $n$ 行，每行包含 $n$ 个以空格分隔的整数（0 或 1），表示邻接矩阵。 最后一行包含若干个以空格分隔的整数，表示初始感染节点集合 initial。

输出格式

输出一个整数，表示应该移除的节点编号。

---

输入输出样例

样例 1

输入：

3
1 1 0
1 1 0
0 0 1
0 1

输出：

0

解释：节点 0 和 1 连通。移除 0，1 仍会感染 0；移除 1，0 仍会感染 1。两者效果一样，返回索引较小的 0。

样例 2

输入：

3
1 0 0
0 1 0
0 0 1
0 2

输出：

0

解释：0 和 2 不连通。移除 0 节省 1 个节点；移除 2 也节省 1 个节点。返回最小索引 0。

样例 3

输入：

3
1 1 1
1 1 1
1 1 1
1 2

输出：

1

解释：所有节点连通。移除任何一个，其他节点都会感染它。返回最小索引 1。

---

数据范围与提示

• $n == graph.length == graph[i].length$
• $2 \le n \le 300$
• $graph[i][j]$ 为 $0$ 或 $1$
• $graph[i][i] == 1$
• $1 \le initial.length \le n$
• initial 中的所有整数互不相同

---

1. 预备知识点

• 图的连通性：理解连通分量（Connected Component）的概念。
• 并查集 (DSU)：高效处理合并与查询连通块大小的数据结构。
• 深度优先搜索 (DFS) / 广度优先搜索 (BFS)：用于遍历图并标记连通块。
• 计数策略：如何通过逻辑判断“拯救”某个连通块。

---

2. 启发式思路引导（草稿纸上的推演）

第一步：理解感染逻辑

• 恶意软件是按“块”传播的。只要一个连通块里有一个初始感染源，整个块都会完蛋。
• 核心观察：如果我们移除节点 $u \in initial$，只有当节点 $u$ 是它所属连通块中唯一的感染源时，这个连通块才可能被“拯救”。

第二步：分类讨论

假设某个连通块 $C$：

1. 含有 0 个感染源：本来就是安全的。
2. 含有 1 个感染源 $u$：如果移除 $u$，整个块 $C$ 的 $size(C)$ 个节点都不会被感染。这是我们优先考虑的情况。
3. 含有 2 个或更多感染源：即使移除其中一个，剩下的感染源依然会毁掉整个块。这种情况下，移除任何一个节点对减少最终感染数没有贡献（贡献为 0）。

第三步：算法流程

1. 找块：找出图中所有的连通块。记录每个连通块的大小。
2. 统计源：对于每个连通块，统计 initial 数组中有多少个节点落在该块内。
3. 计算贡献：遍历 initial 中的节点 $u$：
   • 找到 $u$ 所在的连通块。
   • 如果该块中只有 $u$ 这一个源，则贡献 = 块的大小。
   • 否则，贡献 = 0。
4. 决策：寻找贡献最大的节点。若贡献相同（或全为 0），则取 initial 中索引最小的节点。

---

3. 算法逻辑流程图 (Mermaid)

graph TD
    A["开始: 读入矩阵与 initial 集合"] --> B["初始化并查集 DSU 或进行 DFS 划分连通块"]
    B --> C["统计每个连通块的大小 size{root}"]
    C --> D["遍历 initial, 统计每个块包含的初始感染源数量 count{root}"]
    D --> E["对 initial 数组进行升序排序 (处理索引最小原则)"]
    E --> F["初始化 max_saved 为负数, ans 为 initial{0}"]
    F --> G{"遍历排序后的 initial 节点 u"}
    G -- "遍历结束" --> H["输出 ans"]
    G -- "处理节点 u" --> I["查找 u 所属块的根 root"]
    I --> J{"count{root} 是否等于 1 ?"}
    J -- "是 (唯一源)" --> K["saved 等于 size{root}"]
    J -- "否 (多源或无源)" --> L["saved 等于 0"]
    K --> M{"saved 是否大于 max_saved ?"}
    L --> M
    M -- "是" --> N["更新 max_saved 等于 saved, ans 等于 u"]
    M -- "否" --> G
    N --> G

---

4. 读题关键词与坑点总结

1. “整个连通分量”：这是典型的图论问题，提示我们需要先进行分块处理。
2. “移除恰好一个”：这意味着我们只能做一次决策。
3. “移除不再被感染，但可能被二次感染”：这句话是理解的关键。它告诉你：如果块内还有别的源，你的移除是徒劳的。
4. “索引最小”：这是 NOI 题目中常见的 Breaking Tie（平局判定）要求。建议在处理前先对 initial 排序，或者在比较大小时严格限制条件。
5. 多源块的陷阱：很多学生会误以为移除多源块中的一个也能减少一些感染。实际上，只要还有一个源，整个块就没救。这种情况贡献为 0。

5. 复杂度分析与建议

• 时间复杂度：
  • 构建连通块：若用邻接矩阵，遍历为 $O(n^2)$。
  • 并查集/DFS：$O(n)$ 或 $O(n \alpha(n))$。
  • 统计与遍历：$O(initial.length)$。
  • 总计 $O(n^2)$，对于 $n=300$ 的范围，运行时间远小于 1ms，非常安全。
• 空间复杂度：
  • 需要 $O(n)$ 的空间存储并查集父节点数组、块大小数组、感染源计数数组。
  • $O(n^2)$ 存储原图矩阵。
• 优化建议：对于 $n=300$，直接使用二维数组即可。如果 $n$ 达到 $10^5$，应改用邻接表存储并使用 DSU 优化。注意题目给的是邻接矩阵，读取数据时不要超时。