当前位置：首页 > news >正文

题解：AtCoder AT_awc0081_c Spread of Rumors

news 2026/6/14 11:04:53

【题目来源】

AtCoder：C - Spread of Rumors

【题目描述】

There are \(N\) people, numbered from \(1\) to \(N\). There are a total of \(M\) one-way communication channels among the people. The \(i\)-th communication channel allows person \(U_i\) to send a message to person \(V_i\).

Initially (at the start of day \(0\)), only person \(S\) knows a certain rumor. The spread of the rumor proceeds day by day according to the following rules:

Each person who knows the rumor at the start of day \(d\) (\(d = 0, 1, 2, \ldots\)) simultaneously sends the rumor through all communication channels originating from that person. The sent rumors arrive at the start of day \(d+1\), and the recipients become aware of the rumor from that point onward.
A person who newly learns the rumor at the start of day \(d+1\) can only actually send the rumor from day \(d+1\) onward.
Once a person learns the rumor, they remain aware of it permanently.

Find the day \(d\) when all people first become aware of the rumor. That is, output the smallest \(d\) such that at the start of day \(d\), all people know the rumor for the first time. If all people already know the rumor at the start of day \(0\) (such as when \(N = 1\)), output \(0\). If the rumor cannot reach all people no matter how many days pass, output \(-1\).

有 \(N\) 个人，编号从 \(1\) 到 \(N\)。这些人之间共有 \(M\) 条单向通信信道。第 \(i\) 条通信信道允许人物 \(U_i\) 向人物 \(V_i\) 发送消息。

初始时（在第 \(0\) 天开始时），只有人物 \(S\) 知道某个谣言。谣言的传播按以下规则逐天进行：

在第 \(d\) 天开始时（\(d = 0, 1, 2, \ldots\)）知道谣言的每个人，会同时通过所有从他们出发的通信信道发送谣言。发送的谣言在第 \(d+1\) 天开始时到达，接收者从那时起知道谣言。
在第 \(d+1\) 天开始时新学到谣言的人，只能从第 \(d+1\) 天开始实际发送谣言。
一旦一个人知道谣言，他们将永久保持知情。

求所有人首次都知道谣言的日子 \(d\)。也就是说，输出最小的 \(d\)，使得在第 \(d\) 天开始时，所有人第一次都知道谣言。如果所有人已经在第 \(0\) 天开始时就知道谣言（例如 \(N = 1\) 的情况），输出 \(0\)。如果无论经过多少天，谣言都无法到达所有人，输出 \(-1\)。

【输入】

\(N\) \(M\) \(S\)
\(U_1\) \(V_1\)
\(U_2\) \(V_2\)
\(\vdots\)
\(U_M\) \(V_M\)

The first line contains \(N\) representing the number of people, \(M\) representing the number of communication channels, and \(S\) representing the number of the person who initially knows the rumor, separated by spaces.
Lines \(2\) through \(M + 1\) contain the communication channel information.
The \((1 + i)\)-th line contains \(U_i\) and \(V_i\), separated by spaces, indicating that the \(i\)-th communication channel goes from person \(U_i\) to person \(V_i\).

【输出】

Output in a single line the earliest day \(d\) when all people become aware of the rumor. However, if the rumor cannot spread to all people, output \(-1\).

【输入样例】

【输出样例】

【核心思想】

问题分析：给定 \(N\) 个人和 \(M\) 条单向通信信道，从第 \(S\) 个人开始传播谣言，每天谣言会沿着信道传播一层。求所有人都知道谣言的最小天数 \(d\)。这是一个BFS求最短路的最远距离问题，关键在于谣言传播的时间等于从起点到最远节点的最短路径长度。
算法选择：
- BFS（广度优先搜索）：按层遍历图，计算从起点 \(S\) 到每个节点的最短距离
- 距离数组 dist：记录从起点到每个节点的最短距离，\(-1\) 表示未访问
- 最大距离统计：遍历所有节点，取最大距离作为答案
关键步骤：
- 建图：读取 \(N\)（人数）、\(M\)（信道数）、\(S\)（起点），使用邻接表存储有向图
- BFS计算距离：从起点 \(S\) 开始BFS，计算 dist[i] 表示第 \(i\) 个人知道谣言的最小天数
- 检查可达性：遍历所有节点，若存在 dist[i] == -1，说明有人无法知道谣言，输出 \(-1\)
- 统计答案：取所有 dist[i] 的最大值，即为所有人都知道谣言的最小天数
时间/空间复杂度：
- 时间复杂度：\(O(N + M)\)，BFS遍历所有节点和边一次
- 空间复杂度：\(O(N + M)\)，邻接表和距离数组
BFS求最远距离的核心思想：
- 层序传播：BFS按层扩展，第 \(k\) 层节点距离起点为 \(k\)，对应谣言传播 \(k\) 天
- 第一次访问即最短：由于边权相同（每天传播一层），第一次访问即为最短时间
- 最大距离决定答案：谣言传播到所有人需要的时间等于从起点到最远节点的距离
- 适用于信息传播、谣言扩散、到达所有节点的最短时间类问题

【算法标签】

BFS-一维

【代码详解】

#include <bits/stdc++.h>
using namespace std;
const int N = 400005, M = 200005;
int n, m, s, ans = -1;  // n: 节点数，m: 边数，s: 起点，ans: 最大距离
int h[N], e[M], ne[M], idx;  // 邻接表
int dist[N];  // 距离数组void add(int a, int b)  // 添加有向边
{e[idx] = b, ne[idx] = h[a], h[a] = idx++;  // 将边添加到邻接表
}void bfs()  // 广度优先搜索
{memset(dist, -1, sizeof(dist));  // 初始化距离为-1queue<int> q;  // 创建队列q.push(s);  // 起点入队dist[s] = 0;  // 起点距离为0while (!q.empty())  // 当队列不为空{int u = q.front();  // 取队首q.pop();  // 出队for (int i = h[u]; i != -1; i = ne[i])  // 遍历邻居{int v = e[i];  // 邻居节点if (dist[v] == -1)  // 如果未访问{dist[v] = dist[u] + 1;  // 更新距离q.push(v);  // 入队}}}
}
int main()
{cin >> n >> m >> s;  // 输入节点数、边数、起点memset(h, -1, sizeof(h));  // 初始化邻接表while (m--)  // 处理每条边{int u, v;cin >> u >> v;  // 输入有向边add(u, v);  // 添加边}bfs();  // 执行广度优先搜索for (int i = 1; i <= n; i++)  // 遍历所有节点{if (dist[i] == -1)  // 如果有节点不可达{cout << -1 << endl;  // 输出-1return 0;}ans = max(ans, dist[i]);  // 更新最大距离}cout << ans << endl;  // 输出最大距离return 0;
}

【运行结果】