Overview

If we consider people as vertices and communication methods as directed edges, this problem becomes “finding the shortest distance from the starting point \(S\) to each vertex.” The earliest day each person learns the rumor equals the shortest edge count from \(S\) to that person, so if everyone can be reached, the answer is the maximum of these values; if someone cannot be reached, the answer is \(-1\).

Analysis

The rumor spreads from people who know it on a given day to their neighbors on the next day. In other words,

• Exactly 1 edge is traversed per day
• The earliest day a person first receives the rumor is the “minimum number of edges” from \(S\) to that person

For example, if we have edges:

• \(S \to A\)
• \(A \to B\)
• \(S \to C\)

then:

• \(S\) knows on day \(0\)
• \(A, C\) know on day \(1\)
• \(B\) knows on day \(2\)

This is exactly the shortest distance from the starting point \(S\).

Key Insight

In this problem, edges have no weights, and every communication method takes “1 day” to deliver. Therefore, what we need is the shortest distance in an unweighted directed graph, which can be computed using BFS (Breadth-First Search).

Why a Naive Approach Is Too Slow

“Simulating, for each day, the spread from all people who currently know the rumor” is correct in principle. However, depending on the implementation, it may repeatedly examine all vertices or all edges every day, resulting in extremely slow worst-case performance.

Also, DFS (Depth-First Search) does not guarantee that the first path found is the shortest, so it is not suitable for correctly finding the earliest day each person learns the rumor.

How to Solve It

BFS explores in the order “vertices at distance \(0\) → vertices at distance \(1\) → vertices at distance \(2\) …”. Therefore, the distance when each vertex is first reached is the shortest distance to that vertex.

If we denote this shortest distance as dist[i], then:

• If dist[i] = -1, the rumor never reaches that person
• If everyone is reached, the earliest day everyone knows is \(\max_i dist[i]\)

Algorithm

1. Build an adjacency list with people as vertices and communication methods as directed edges.
2. Initialize the array dist to -1.
3. Set dist[S] = 0 for the starting point S and enqueue it.
4. Perform BFS:
   • Dequeue a vertex u
   • For each vertex v reachable from u, if it is still unvisited:
     • dist[v] = dist[u] + 1
     • Enqueue v
5. After BFS completes:
   • If there is even one person with dist[i] = -1, output -1
   • Otherwise, output the maximum value of dist

Why This Is Correct

• Since the rumor traverses exactly 1 edge per day, the earliest day it reaches a person is the shortest edge count.
• BFS explores in order of increasing edge count, so dist[i] equals the shortest edge count from \(S\) to \(i\).
• The day everyone knows the rumor is the day it reaches the last person. Therefore, the answer is the maximum of the shortest distances.
• If there is an unreachable person, the rumor will never spread to everyone.

Complexity

• Time complexity: \(O(N + M)\)
• Space complexity: \(O(N + M)\)

Implementation Notes

• The graph is a directed graph, so only add edges in the direction u -> v.

• Since we are finding shortest distances, use BFS with a queue.

• Initializing dist to -1 is convenient because it allows a single array to serve both purposes:

  • Checking whether a vertex has been reached
  • Recording the number of days to reach it

• At the end, by examining dist, if any person is unreachable, we can immediately output -1.

  Source Code

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, M, S = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v = map(int, input().split())
        graph[u].append(v)

    dist = [-1] * (N + 1)
    dist[S] = 0
    q = deque([S])

    while q:
        u = q.popleft()
        du = dist[u]
        for v in graph[u]:
            if dist[v] == -1:
                dist[v] = du + 1
                q.append(v)

    ans = 0
    for i in range(1, N + 1):
        if dist[i] == -1:
            print(-1)
            return
        if dist[i] > ans:
            ans = dist[i]

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.