概要

記録を先頭から順番に見て、「その時点で噂を知っている生徒」だけが次の生徒に噂を伝えられる、とそのままシミュレーションする問題です。
生徒 \(0\) だけを最初に知っている状態にして、各記録を 1 回ずつ処理すれば答えが求まります。

考察

この問題で大事なのは、記録は与えられた順番どおりに処理される という点です。

たとえば、次のような記録を考えます。

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

最初に噂を知っているのは生徒 \(0\) だけです。

1. 記録 \((1, 2)\) を処理する時点では、生徒 \(1\) はまだ噂を知りません。
   したがって、生徒 \(2\) には伝わりません。
2. 次に記録 \((0, 1)\) を処理すると、生徒 \(1\) が噂を知ります。

最終的に噂を知っているのは生徒 \(0,1\) の 2 人であり、生徒 \(2\) には伝わりません。

つまり、この問題は単純なグラフの到達可能性ではありません。
「辺があるなら最終的に伝わる」と考えて BFS や DFS をすると、順番の情報を無視してしまい誤答になります。

---

ではどうするかというと、問題文のルールをそのまま実装すれば十分です。

• known[i] = True なら「生徒 \(i\) は噂を知っている」
• 最初は known[0] = True
• 各記録 \((a, b)\) について
  • もし known[a] が True なら known[b] = True
  • そうでなければ何もしない

この方法なら、記録を処理するたびに最新の状態が反映されるので、後の記録で新しく噂を伝えられるようになる場合も正しく扱えます。

素朴に「何度も全記録を見直して変化がなくなるまで繰り返す」ような実装も考えられますが、この問題では記録の順番が固定されており、1 回順に見るだけで十分です。
何周もする必要はなく、余計な計算を避けられます。

アルゴリズム

1. 長さ \(N\) の真偽値配列 known を用意し、すべて False で初期化する。
2. 生徒 \(0\) だけ最初から噂を知っているので、known[0] = True とする。
3. 記録を先頭から順に読む。
   • 記録が \((a, b)\) のとき、known[a] が True なら known[b] = True にする。
4. 最後に True になっている人数、つまり sum(known) を出力する。

具体例

例えば、

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

とします。

最初:
known = [True, False, False, False]

• \((0, 2)\) を処理
  生徒 \(0\) は知っているので、生徒 \(2\) も知る
  known = [True, False, True, False]

• \((1, 3)\) を処理
  生徒 \(1\) はまだ知らないので、何も起こらない
  known = [True, False, True, False]

• \((2, 1)\) を処理
  生徒 \(2\) は知っているので、生徒 \(1\) も知る
  known = [True, True, True, False]

最終的に 3 人が噂を知っています。

計算量

• 時間計算量: \(O(M)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 生徒が噂を知っているかどうかは、真偽値配列 known で管理すると簡単です。

• 記録は必ず入力順に処理します。

• 最後の人数は、Python では True を \(1\)、False を \(0\) とみなすので sum(known) で数えられます。

• 入力が大きいので、input = sys.stdin.readline を使うと高速です。

  ソースコード

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

---

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