概要

\(N\) 人の生徒の中で、最初に出席番号 \(0\) の生徒だけが知っている「噂」が、\(M\) 個の伝達記録に基づいてどのように広がっていくかをシミュレーションする問題です。最終的に何人が噂を知っているかを求めます。

考察

この問題を解くための重要なポイントは、「記録は与えられた順序（時系列）で処理される」という点です。

例えば、生徒 \(0, 1, 2\) がいて、以下の 2 つの記録がある場合を考えてみます。 1. \((1, 2)\): 生徒 \(1\) が生徒 \(2\) に伝える 2. \((0, 1)\): 生徒 \(0\) が生徒 \(1\) に伝える

この場合、最初の時点で噂を知っているのは生徒 \(0\) だけです。 - 記録 1 の時点では、生徒 \(1\) は噂を知らないため、生徒 \(2\) には伝わりません。 - 記録 2 の時点で、生徒 \(0\) が噂を知っているため、生徒 \(1\) に伝わります。 結果、噂を知っているのは生徒 \(0, 1\) の \(2\) 人になります。

もし記録の順序が逆であれば、生徒 \(0 \to 1 \to 2\) と伝わり、全員が知ることになります。このように、「その瞬間に送り手が噂を知っているか」を順番に判定していく必要があります。

一度噂を知った生徒は、それ以降の記録において常に「伝える側」になることができるため、各生徒の状態を「噂を知っているか（True）」「知らないか（False）」の 2 値で管理すれば十分です。

アルゴリズム

1. 状態の初期化:

   • 長さ \(N\) の真偽値配列 knows を作成し、すべて False で初期化します。
   • 出席番号 \(0\) の生徒は最初から知っているので、 knows[0] = True とします。

2. 記録の処理:

   • \(M\) 個の記録 \((a_i, b_i)\) を入力された順番に 1 つずつ見ていきます。
   • もし knows[a_i] が True であれば、 knows[b_i] を True に更新します。
   • knows[a_i] が False であれば、何も行いません。

3. 集計:

   • すべての記録を処理した後、 knows 配列の中で True になっている要素の数を数えます。

計算量

• 時間計算量: \(O(N + M)\)
  • 配列の初期化に \(O(N)\)、記録の処理に \(O(M)\)、最後の集計に \(O(N)\) かかります。制約の \(N, M \leq 2 \times 10^5\) に対して十分に高速です。
• 空間計算量: \(O(N)\)
  • 生徒の状態を保存するための配列 knows のサイズが \(N\) です。

実装のポイント

• 高速な入出力: \(M\) が最大 \(10^5\) と大きいため、Python では input() を繰り返すよりも sys.stdin.read().split() などを使って一括で読み込む方が実行時間を短縮できます。

• 真偽値の合計: Python では sum([True, False, True]) のように真偽値のリストを sum() 関数に渡すと、True を \(1\)、False を \(0\) としてカウントしてくれるため、簡潔に合計人数を求めることができます。

  ソースコード

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()

この解説は gemini-3-flash-thinking によって生成されました。