Overview

This is a problem where, among \(N\) students, a “rumor” initially known only by student number \(0\) spreads based on \(M\) transmission records, and we need to simulate how it propagates. We are asked to determine how many students know the rumor in the end.

Analysis

The key point for solving this problem is that “the records are processed in the given order (chronologically)”.

For example, consider the case where there are students \(0, 1, 2\) and the following 2 records: 1. \((1, 2)\): Student \(1\) tells student \(2\) 2. \((0, 1)\): Student \(0\) tells student \(1\)

In this case, initially only student \(0\) knows the rumor. - At record 1, student \(1\) does not know the rumor, so it is not passed to student \(2\). - At record 2, student \(0\) knows the rumor, so it is passed to student \(1\). As a result, the students who know the rumor are students \(0\) and \(1\), totaling \(2\) people.

If the order of the records were reversed, the rumor would spread as \(0 \to 1 \to 2\), and everyone would know it. In this way, we need to check in order “whether the sender knows the rumor at that moment”.

Once a student learns the rumor, they can always act as a “sender” in subsequent records. Therefore, it is sufficient to manage each student’s state as a binary value: “knows the rumor (True)” or “does not know (False)”.

Algorithm

1. State Initialization:

   • Create a boolean array knows of length \(N\) and initialize all entries to False.
   • Since student number \(0\) knows the rumor from the beginning, set knows[0] = True.

2. Processing Records:

   • Go through the \(M\) records \((a_i, b_i)\) one by one in the given input order.
   • If knows[a_i] is True, update knows[b_i] to True.
   • If knows[a_i] is False, do nothing.

3. Counting:

   • After processing all records, count the number of elements in the knows array that are True.

Complexity

• Time Complexity: \(O(N + M)\)
  • Initializing the array takes \(O(N)\), processing the records takes \(O(M)\), and the final counting takes \(O(N)\). This is sufficiently fast for the constraints \(N, M \leq 2 \times 10^5\).
• Space Complexity: \(O(N)\)
  • The size of the array knows for storing the students’ states is \(N\).

Implementation Notes

• Fast I/O: Since \(M\) can be as large as \(10^5\), in Python it is faster to read all input at once using sys.stdin.read().split() rather than calling input() repeatedly, which reduces execution time.

• Summing Booleans: In Python, passing a list of booleans to the sum() function, such as sum([True, False, True]), counts True as \(1\) and False as \(0\), allowing us to concisely compute the total number of people.

  Source Code

import sys

def main():
    # 入力をすべて読み込み、空白（スペースや改行）で分割してリストにする
    # 大量の入力がある場合に高速に処理するための手法です
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # イテレータを使用して順番に値を取得する
    it = iter(input_data)
    
    # 生徒数 N と 記録の数 M を取得
    N = int(next(it))
    M = int(next(it))
    
    # 各生徒が噂を知っているかどうかを管理する配列（初期値はすべて False）
    # 出席番号 0 から N-1 までの情報を保持する
    knows = [False] * N
    
    # 最初、出席番号 0 の生徒だけが噂を知っている
    knows[0] = True
    
    # M 件の記録を時系列順に処理する
    for _ in range(M):
        # a: 噂を伝える側の生徒, b: 噂を伝えられる側の生徒
        a = int(next(it))
        b = int(next(it))
        
        # もし現時点で生徒 a が噂を知っていれば、生徒 b も噂を知っている状態になる
        if knows[a]:
            knows[b] = True
            
    # 全ての処理が終わった後、噂を知っている生徒（True の要素）の総数をカウントして出力
    # Pythonでは sum() をブール値のリストに適用すると True を 1, False を 0 として計算します
    print(sum(knows))

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3-flash-thinking.