Overview

This problem is a straightforward simulation where you process the records in order from the beginning: only “students who know the rumor at that point” can pass the rumor to the next student.
Start with only student \(0\) knowing the rumor, then process each record once to obtain the answer.

Analysis

The key point of this problem is that records are processed in the given order.

For example, consider the following records:

• \((1, 2)\)
• \((0, 1)\)

Initially, only student \(0\) knows the rumor.

1. When processing record \((1, 2)\), student \(1\) does not yet know the rumor.
   Therefore, the rumor is not passed to student \(2\).
2. Next, when processing record \((0, 1)\), student \(1\) learns the rumor.

In the end, only students \(0, 1\) — a total of 2 people — know the rumor, and student \(2\) does not learn it.

In other words, this problem is not simply about reachability in a graph.
If you think “the rumor will eventually spread as long as there’s an edge” and use BFS or DFS, you ignore the ordering information and get a wrong answer.

---

So what should we do? Simply implementing the rules described in the problem statement is sufficient.

• known[i] = True means “student \(i\) knows the rumor”
• Initially, known[0] = True
• For each record \((a, b)\):
  • If known[a] is True, set known[b] = True
  • Otherwise, do nothing

With this approach, the latest state is reflected each time a record is processed, so cases where a later record can newly spread the rumor are handled correctly.

One might also consider a naive implementation that “repeatedly scans through all records until no changes occur,” but in this problem the order of records is fixed, and a single pass through them in order is sufficient.
There is no need for multiple passes, and unnecessary computation is avoided.

Algorithm

1. Prepare a boolean array known of length \(N\), initialized entirely to False.
2. Since only student \(0\) knows the rumor from the start, set known[0] = True.
3. Read the records in order from the beginning.
   • For a record \((a, b)\), if known[a] is True, set known[b] = True.
4. Output the number of people with True, i.e., sum(known).

Concrete Example

For example, suppose:

• \(N = 4\)
• Records:
  • \((0, 2)\)
  • \((1, 3)\)
  • \((2, 1)\)

Initially:
known = [True, False, False, False]

• Process \((0, 2)\)
  Student \(0\) knows the rumor, so student \(2\) learns it
  known = [True, False, True, False]

• Process \((1, 3)\)
  Student \(1\) does not yet know the rumor, so nothing happens
  known = [True, False, True, False]

• Process \((2, 1)\)
  Student \(2\) knows the rumor, so student \(1\) learns it
  known = [True, True, True, False]

In the end, 3 people know the rumor.

Complexity

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

Implementation Notes

• Tracking whether each student knows the rumor is easily managed with a boolean array known.

• Records must be processed strictly in input order.

• For the final count, in Python True is treated as \(1\) and False as \(0\), so you can count with sum(known).

• Since the input can be large, using input = sys.stdin.readline improves speed.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    known = [False] * N
    known[0] = True

    for _ in range(M):
        a, b = map(int, input().split())
        if known[a]:
            known[b] = True

    print(sum(known))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.