概要

記録を先頭から順に見て、「その時点で噂を知っている人だけが次の人に伝えられる」という条件をそのままシミュレーションする問題です。
各生徒が噂を知っているかどうかを管理すれば、最後の人数を効率よく求められます。

考察

この問題の本質は 「記録の順番が重要」 という点です。
たとえば、記録が

1. \((1,2)\)
   
2. \((0,1)\)

だった場合、1番目の時点では生徒1はまだ知らないので生徒2には伝わりません。
その後2番目で生徒1が知っても、もう1番目の記録には戻れないため、生徒2は最後まで知らないままです。

つまり、グラフを作って単純に「0から到達できる頂点数」を数えるだけでは不正解（WA）になります。
時系列どおりに1回ずつ処理する必要があります。

素朴に「記録ごとに噂が広がるかを更新」する方針は正しく、さらに各記録でやることは定数時間です：

• \(a_i\) が知っているなら \(b_i\) を知っている状態にする
• そうでなければ何もしない

これを \(M\) 件ぶん繰り返せばよいです。

アルゴリズム

1. 長さ \(N\) の真偽値配列 know を用意し、全員 False で初期化。
2. 最初に知っているのは生徒0だけなので know[0] = True。
3. 現在知っている人数 cnt = 1 とする。
4. 各記録 \((a,b)\) を順に処理：
   • know[a] が True かつ know[b] が False なら、
     • know[b] = True
     • cnt += 1
   • それ以外は何もしない。
5. 最後に cnt を出力。

この方法なら、記録順の条件を厳密に満たしつつ高速に解けます。

計算量

• 時間計算量: \(O(M)\)
  （各記録を1回ずつ、定数時間で処理）
• 空間計算量: \(O(N)\)
  （噂を知っているかどうかの配列）

実装のポイント

• know[b] がすでに True のときに cnt を増やさないこと（重複加算防止）。

• 入力サイズが大きいので sys.stdin.readline を使うと安全です。

• \(M=0\) の場合でも、生徒0は必ず知っているため答えは1です（この実装は自然に対応済み）。

  ソースコード

import sys

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

    for _ in range(M):
        a, b = map(int, input().split())
        if know[a] and not know[b]:
            know[b] = True
            cnt += 1

    print(cnt)

if __name__ == "__main__":
    main()

この解説は gpt-5.3-codex によって生成されました。