概要

最初に生徒 \(0\) だけが噂を知っている状態から、\(M\) 件の伝達記録を順番に処理し、最終的に噂を知っている生徒の人数を求めるシミュレーション問題です。

考察

この問題のポイントは以下の通りです。

• 噂の伝達は順序が重要です。記録は \(i = 1, 2, \ldots, M\) の順に処理され、ある記録で新たに噂を知った生徒は、それ以降の記録で噂を伝える側になれます。
• 各記録 \((a_i, b_i)\) の処理は非常にシンプルです。「\(a_i\) が噂を知っているなら \(b_i\) も知る」というだけです。
• 制約を見ると \(M \leq 10^5\) なので、\(M\) 件の記録を1件ずつ愚直にシミュレーションしても十分間に合います。

具体例で確認しましょう。

例えば \(N = 4\), \(M = 3\) で記録が \((0, 1), (1, 2), (3, 0)\) の場合：

1. \((0, 1)\)：生徒 \(0\) は噂を知っている → 生徒 \(1\) も噂を知る。知っている人: \(\{0, 1\}\)
2. \((1, 2)\)：生徒 \(1\) は噂を知っている（さっき知った）→ 生徒 \(2\) も噂を知る。知っている人: \(\{0, 1, 2\}\)
3. \((3, 0)\)：生徒 \(3\) は噂を知らない → 何も起こらない。知っている人: \(\{0, 1, 2\}\)

最終的な答えは \(3\) 人です。

アルゴリズム

1. サイズ \(N\) のブール配列 knows を用意し、knows[0] = True（生徒 \(0\) だけが噂を知っている）とする。
2. \(M\) 件の記録を順番に読み込み、各記録 \((a_i, b_i)\) について：
   • knows[a] が True なら、knows[b] を True にする。
   • knows[a] が False なら、何もしない。
3. 最後に knows 配列で True になっている要素の個数を出力する。

つまり、問題文の指示をそのままコードに落とし込む素直なシミュレーションです。

計算量

• 時間計算量: \(O(N + M)\)
  • 配列の初期化に \(O(N)\)、\(M\) 件の記録の処理に \(O(M)\)、最後の集計に \(O(N)\)
• 空間計算量: \(O(N)\)
  • 噂を知っているかどうかを管理するブール配列のサイズ

実装のポイント

• 各生徒が噂を知っているかどうかをブール配列で管理することで、各記録の処理が \(O(1)\) で行えます。

• 記録の処理順序が結果に影響するため、必ず入力順に処理する必要があります。順序を変えると異なる結果になり得ます。

• sum(knows) は Python で True を \(1\)、False を \(0\) として扱うため、True の個数をそのまま数えられます。

  ソースコード

N, M = map(int, input().split())
knows = [False] * N
knows[0] = True
for _ in range(M):
    a, b = map(int, input().split())
    if knows[a]:
        knows[b] = True
print(sum(knows))

この解説は claude4.6opus-thinking によって生成されました。