概要

最初に噂を知っている生徒集合を持ち、各グループワークを予定順に処理して「どちらかが知っていれば両方が知る」をその場で反映し、最終的に知っている人数を数えます。

考察

この問題のポイントは、「グループワークが 順番通り に行われる」ことです。
同じペアの集合でも順番が違うと結果が変わるため、最終的な無向グラフだけ見て連結成分で判断する（Union-Find する）方法は誤りになります。

例えば、初期で 1 のみが知っているとして、

• 1回目: (2,3)
• 2回目: (1,2)

の順なら、1回目終了時点では誰も新しく知らないので (2,3) は変化なし、2回目で 2 が知るだけで 3 は最後まで知りません。
しかし「辺があるから 1-2-3 は連結、全員知る」としてしまうと WA になります。

一方で、噂を知っているかどうかは一度 true になったら二度と false には戻らない（単調増加）ので、各回のペア (a,b) について

• もし a または b が噂を知っているなら、処理後は両方が知る

をそのまま順にシミュレーションすれば十分です。これなら追加の伝播（何度も全体を見直す）も不要で、\(M \le 2\times 10^5\) でも間に合います。

素朴に「変化がなくなるまで全ペアを何度もなめる」ような実装をすると、最悪で \(O(MN)\) 近くまで膨らみ TLE になり得ますが、本問は「一回ずつ順に処理」すれば良い形になっています。

アルゴリズム

1. 長さ \(N\) の配列 known を用意し、known[i]=1 なら生徒 \(i\) が噂を知っているとする。
2. 初期状態として、出席番号 \(1 \sim K\) を known=1 にする。
3. \(i=1\) から \(M\) 回目まで順に、ペア \((A_i, B_i)\) を読む。
   • もし known[A_i]==1 または known[B_i]==1 なら、known[A_i]=known[B_i]=1 にする。
4. 最後に known[1..N] の合計を出力する。

この処理は各グループワークにつき定数時間で完了します。

計算量

• 時間計算量: \(O(N + M)\)（初期化と \(M\) 回の更新、最後の合計）
• 空間計算量: \(O(N)\)（known 配列）

実装のポイント

• 生徒番号が \(1\) 始まりなので、配列は N+1 要素にして known[1]〜known[N] を使うと安全です。

• Python では bytearray を使うと真偽配列を高速・省メモリで扱えます（0/1 を格納）。

• 入力サイズが大きいので、sys.stdin.buffer.read().split() の一括読み込みで高速化しています。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    M = int(next(it))
    K = int(next(it))

    known = bytearray(N + 1)
    known[1:K + 1] = b'\x01' * K

    for _ in range(M):
        a = int(next(it))
        b = int(next(it))
        if known[a] or known[b]:
            known[a] = 1
            known[b] = 1

    print(sum(known[1:]))

if __name__ == "__main__":
    main()

---

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