红色传播模拟：宣传路线信息扩散 完整解题档案

档案概况

题目、题干与输入输出

正式题面

源文件：official-prompt.md

规则来源

• 赛项说明页码：10
• 训练题主题：红色传播模拟：宣传路线信息扩散
• 所属赛道：红色文化赛道

题目背景

宣传队从一个起点纪念站出发传播活动信息。每天，已经获知信息的站点会把消息传递给相邻站点。需要统计消息扩散到全图的过程。

任务描述

• 读取站点数量、连接关系和起始传播站点。
• 按“每天向相邻站点扩散一层”的规则模拟传播。
• 计算每个站点最早在哪一天收到消息。
• 输出总传播天数、所有节点的到达日以及未触达节点数量。

输入格式

1. 第一行输入 n m start。
2. 接下来 m 行，每行输入 u v，表示无向连接。

输出格式

1. 第一行输出 total_days=最大到达日；若只有起点则可以为 0。
2. 第二行输出 days= 后接 1..n 号节点的最早到达日，用空格分隔；未到达记为 -1。
3. 第三行输出 unreached=未触达节点数。

数据范围与说明

• 1 <= n <= 10^5，0 <= m <= 2*10^5。
• 图为无向图，允许存在重边和自环，自环不影响结果。
• 传播每天扩散一层，因此本质上是无权图最短路。

样例输入

5 4 1
1 2
1 3
2 4
3 5

样例输出

total_days=2
days=0 1 1 2 2
unreached=0

样例解释

• 第 0 天只有 1 号站点已知消息。
• 第 1 天扩散到 2、3 号站点，第 2 天扩散到 4、5 号站点。
• 因此总传播天数为 2，所有节点都被触达。

知识点清单

• 无权图最短路。
• 广度优先搜索 BFS。
• 层次遍历与到达日。
• 未访问节点标记。
• 图传播模型的程序化表示。

约束拆解

源文件：parsed-constraints.md

显式约束

• 1 <= n <= 10^5，0 <= m <= 2*10^5。
• 图为无向图，允许存在重边和自环，自环不影响结果。
• 传播每天扩散一层，因此本质上是无权图最短路。

建模拆解

• 先明确输入的实体和字段，再把它们翻译成 广度优先搜索 BFS 需要的数据结构。
• 把输出中每一项指标都和中间变量对应起来，避免最后临时拼装。
• 先用样例手推一次，再确认边界条件是否都能走到正确分支。

易错边界

• 图可能不连通，未触达节点要保留为 -1。
• 起点本身的到达日是 0。
• 存在重边时不能重复入队同一节点。

计分模型

源文件：scoring-model.md

判题方式

• 主判题方式：simulation
• 主算法：广度优先搜索 BFS

判题重点

• 重点校验状态更新顺序、触发条件和逐轮迭代是否符合题意。
• 隐藏数据会覆盖临界阈值、连续触发和无触发三类情形。

公开样例建议

• 至少准备 1 组题面样例、2 组边界样例和 2 组自定义回归样例。
• 多输出题必须验证所有字段都来自同一套方案。

隐藏数据建议

• 验证完全不连通图和只有一个节点的图。
• 验证存在重边、自环时的访问稳定性。
• 验证起点不在 1 号节点时的输出顺序。

验收清单

源文件：acceptance-checklist.md

• 正式题面、约束拆解、评分说明均已补齐
• 样例输入输出已定义并通过主实现校验
• python 主实现已提供并与样例输出对齐
• cpp 主实现已提供并与样例输出对齐
• 调试记录、决策记录、验证计划已补齐
• 可由 20-tools/assemble_case_dossiers.py 汇总为完整解题档案

样例输入输出

样例输入：sample.in

5 4 1
1 2
1 3
2 4
3 5

样例输出：sample.out

total_days=2
days=0 1 1 2 2
unreached=0

题解、建模与最终解法

自动整理的解题流程

• 题目主题：红色传播模拟：宣传路线信息扩散
• 题目摘要：在无向图上模拟信息逐日传播，输出全部节点获知消息所需天数和每个节点的最早到达日。
• 判题提示：该题以流程模拟为主，重点是状态更新顺序、异常分支和终止条件。
• 把题目拆成状态变量和逐步更新规则，明确每轮输入、状态变化和终止条件。
• 优先用样例手推每一步状态，避免分支条件顺序与题意相反。

解题思路

源文件：solution-rationale.md

1. 问题重述

在无向图上模拟信息逐日传播，输出全部节点获知消息所需天数和每个节点的最早到达日。

2. 数据结构与建模

• 主算法：广度优先搜索 BFS
• 输入拆解后对应的数据结构要和输出项一一对应。
• 需要重点维护的状态包括：题目实体、核心指标、中间结果和最终答案。

3. 算法步骤

1. 建立无向图邻接表。
2. 从起点开始做 BFS，并记录每个节点的到达日。
3. 所有首次入队的节点，其到达日等于前驱节点到达日加一。
4. 遍历完成后统计最大到达日和未触达节点数。

4. 正确性说明

• 每一步都严格对应题面给出的规则或约束。
• 所有输出字段都来自同一份计算过程，不会出现“各算各的”的不一致情况。
• 边界情况通过单独分支或统一规则处理，保证程序在最小规模和重复值情况下也稳定。

5. 复杂度分析

• 复杂度取决于输入规模和主算法，但整体设计保持在初中组可讲解、可验证的范围内。
• 只保留必要状态，不引入超出题意的数据结构。

6. 易错点

• 图可能不连通，未触达节点要保留为 -1。
• 起点本身的到达日是 0。
• 存在重边时不能重复入队同一节点。

7. 知识点清单

• 无权图最短路。
• 广度优先搜索 BFS。
• 层次遍历与到达日。
• 未访问节点标记。
• 图传播模型的程序化表示。

设计决策记录

源文件：decision-log.md

• 选择 广度优先搜索 BFS 作为主算法，因为它能直接覆盖题目的核心约束。
• 传播过程天然按层扩散，BFS 是最直接的模型。
• 直接记录到达日，可以同时覆盖总天数和逐点输出需求。
• Python 与 C++ 版本统一输出格式，便于双语训练和证据采集。

验证计划

源文件：validation-plan.md

• 先验证题面公开样例，确保基础流程无误。
• 验证完全不连通图和只有一个节点的图。
• 验证存在重边、自环时的访问稳定性。
• 验证起点不在 1 号节点时的输出顺序。
• 最后再补 1 组手工构造的极小数据，确认程序不会依赖特殊输入规模。

备选方案

源文件：alternatives.md

最终代码与实现

Python 主实现

源文件：main.py

• 实现状态：当前已有可执行实现

from collections import deque
import sys


def solve(data: str) -> str:
    tokens = list(map(int, data.split()))
    if not tokens:
        return ""
    it = iter(tokens)
    n = next(it)
    m = next(it)
    start = next(it)
    graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        u = next(it)
        v = next(it)
        graph[u].append(v)
        graph[v].append(u)
    days = [-1] * (n + 1)
    days[start] = 0
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if days[nxt] != -1:
                continue
            days[nxt] = days[node] + 1
            queue.append(nxt)
    reach = days[1:]
    total_days = max(reach)
    unreached = sum(1 for value in reach if value == -1)
    return "\n".join(
        [
            f"total_days={total_days}",
            "days=" + " ".join(map(str, reach)),
            f"unreached={unreached}",
        ]
    )


if __name__ == "__main__":
    sys.stdout.write(solve(sys.stdin.read()).strip())
    sys.stdout.write("\n")

C++ 对照实现

源文件：main.cpp

• 实现状态：当前已有可执行实现

#include <deque>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, start;
    if (!(cin >> n >> m >> start)) {
        return 0;
    }
    vector<vector<int>> graph(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    vector<int> days(n + 1, -1);
    deque<int> q;
    days[start] = 0;
    q.push_back(start);
    while (!q.empty()) {
        int node = q.front();
        q.pop_front();
        for (int nxt : graph[node]) {
            if (days[nxt] != -1) {
                continue;
            }
            days[nxt] = days[node] + 1;
            q.push_back(nxt);
        }
    }
    int total_days = 0;
    int unreached = 0;
    for (int i = 1; i <= n; ++i) {
        if (days[i] == -1) {
            ++unreached;
        } else if (days[i] > total_days) {
            total_days = days[i];
        }
    }
    cout << "total_days=" << total_days << "\n";
    cout << "days=";
    for (int i = 1; i <= n; ++i) {
        if (i > 1) {
            cout << ' ';
        }
        cout << days[i];
    }
    cout << "\n";
    cout << "unreached=" << unreached << "\n";
    return 0;
}

代码执行与运行结果

最新成功运行

PY 运行输出摘录

total_days=2
days=0 1 1 2 2
unreached=0

CPP 运行输出摘录

total_days=2
days=0 1 1 2 2
unreached=0

全部运行记录索引

调试、修正与流程留痕

调试日志

源文件：debug-journal.md

失败案例目录

源文件：failure-catalog.md

编码过程记录

源文件：implementation-journal.md

全流程文件导航

• 题目总览：s2-jh-03-propagation-sim/README.md
• 题面与约束：official-prompt.md、parsed-constraints.md、scoring-model.md、acceptance-checklist.md
• 代码与样例：10-cases/s2-jh-03-propagation-sim/02-solution
• 运行证据：10-cases/s2-jh-03-propagation-sim/03-execution
• 调试过程：debug-journal.md、failure-catalog.md、implementation-journal.md
• 解法说明：solution-rationale.md、decision-log.md、validation-plan.md、alternatives.md
• 交付档案：final-report.md、appendix-code.md、appendix-runs.md、evidence-pack.md