Overview

Starting from a state where only student \(0\) knows the rumor, process \(M\) transmission records in order and determine the number of students who know the rumor at the end. This is a simulation problem.

Analysis

The key points of this problem are as follows:

• Order matters for rumor transmission. Records are processed in order \(i = 1, 2, \ldots, M\), and a student who newly learns the rumor from a certain record can pass it on in subsequent records.
• Processing each record \((a_i, b_i)\) is very simple: “If \(a_i\) knows the rumor, then \(b_i\) also learns it.”
• Looking at the constraints, \(M \leq 10^5\), so straightforwardly simulating the \(M\) records one by one is fast enough.

Let’s verify with a concrete example.

For instance, with \(N = 4\), \(M = 3\) and records \((0, 1), (1, 2), (3, 0)\):

1. \((0, 1)\): Student \(0\) knows the rumor → Student \(1\) also learns the rumor. Those who know: \(\{0, 1\}\)
2. \((1, 2)\): Student \(1\) knows the rumor (just learned it) → Student \(2\) also learns the rumor. Those who know: \(\{0, 1, 2\}\)
3. \((3, 0)\): Student \(3\) does not know the rumor → Nothing happens. Those who know: \(\{0, 1, 2\}\)

The final answer is \(3\) students.

Algorithm

1. Prepare a boolean array knows of size \(N\), and set knows[0] = True (only student \(0\) knows the rumor).
2. Read the \(M\) records in order, and for each record \((a_i, b_i)\):
   • If knows[a] is True, set knows[b] to True.
   • If knows[a] is False, do nothing.
3. Finally, output the number of elements that are True in the knows array.

In other words, this is a straightforward simulation that directly translates the problem statement into code.

Complexity

• Time complexity: \(O(N + M)\)
  • \(O(N)\) for array initialization, \(O(M)\) for processing the \(M\) records, and \(O(N)\) for the final count.
• Space complexity: \(O(N)\)
  • The size of the boolean array that tracks whether each student knows the rumor.

Implementation Notes

• By managing whether each student knows the rumor with a boolean array, each record can be processed in \(O(1)\).

• Since the processing order of records affects the result, they must be processed in input order. Changing the order may lead to different results.

• sum(knows) works in Python because True is treated as \(1\) and False as \(0\), so it directly counts the number of True values.

  Source Code

N, M = map(int, input().split())
knows = [False] * N
knows[0] = True
for _ in range(M):
    a, b = map(int, input().split())
    if knows[a]:
        knows[b] = True
print(sum(knows))

This editorial was generated by claude4.6opus-thinking.