概要

噂を知っている生徒がグループワークのペアを通じて順番に噂を広めていく様子をシミュレーションし、最終的に噂を知っている生徒の人数を求める問題です。

考察

重要な気づき

この問題のポイントはグループワークが順番通りに行われるという点です。噂の伝播は時系列に依存します。

例えば、以下のケースを考えましょう：

• \(N = 4, M = 2, K = 1\)（生徒1が最初に噂を知っている）
• グループワーク1: 生徒2と生徒3がペア
• グループワーク2: 生徒1と生徒2がペア

この場合： 1. グループワーク1の時点では、生徒2も生徒3も噂を知らないので、何も起きません。 2. グループワーク2で、生徒1（噂を知っている）と生徒2がペアになるので、生徒2が噂を知ります。

最終的に噂を知っているのは生徒1と生徒2の 2人 です。もし順番が逆なら結果は変わります。このように、順番を無視してはいけないことが重要です。

アプローチ

グループワークの回数 \(M\) が最大 \(2 \times 10^5\) と十分小さいため、各グループワークを1つずつ順番にシミュレーションするだけで十分間に合います。

各グループワークでは、ペアのどちらか一方でも噂を知っていれば、両方が噂を知っている状態に更新します。

アルゴリズム

1. 長さ \(N+1\) の配列 knows を用意し、出席番号 \(1\) から \(K\) までの生徒を True（噂を知っている）に初期化する。
2. \(M\) 回のグループワークを順番に処理する：
   • ペア \((A_i, B_i)\) を読み取る。
   • knows[A_i] または knows[B_i] のいずれかが True なら、両方を True にする。
3. 最後に knows 配列中の True の個数を数えて出力する。

具体例（\(N=5, M=3, K=2\)、つまり生徒1,2が最初に噂を知っている場合）：

グループワーク	ペア	噂を知っている生徒
初期状態	-	{1, 2}
1回目	(2, 4)	{1, 2, 4}（生徒2が知っているので生徒4に伝わる）
2回目	(3, 5)	{1, 2, 4}（どちらも知らないので変化なし）
3回目	(4, 5)	{1, 2, 4, 5}（生徒4が知っているので生徒5に伝わる）

答え: 4

計算量

• 時間計算量: \(O(N + M)\)
  • 初期化に \(O(N)\)、各グループワークの処理に \(O(1)\) で合計 \(O(M)\)、最後の集計に \(O(N)\)
• 空間計算量: \(O(N)\)
  • knows 配列の分

実装のポイント

• 生徒の出席番号が \(1\) から始まるため、配列を \(N+1\) の大きさで確保して 1-indexed でアクセスすると実装が楽です。

• knows 配列を bool 型で管理し、sum(knows) で True の個数を数えられます（Python では True は 1、False は 0 として加算されます）。

• グループワークの順序が結果に影響するため、必ず入力された順番通りに処理する必要があります。

  ソースコード

import sys
input = sys.stdin.readline

def main():
    N, M, K = map(int, input().split())
    
    # knows[i] = True if student i knows the rumor
    knows = [False] * (N + 1)
    for i in range(1, K + 1):
        knows[i] = True
    
    for _ in range(M):
        a, b = map(int, input().split())
        if knows[a] or knows[b]:
            knows[a] = True
            knows[b] = True
    
    print(sum(knows))

main()

---

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