概要

この問題は、出席番号 \(1\) から \(K\) 番の生徒から始まった「噂」が、全 \(M\) 回のグループワーク（ペア作業）を通じてどのように広がっていくかをシミュレーションする問題です。

考察

この問題を解くための重要なポイントは以下の3点です。

1. 状態の変化: 一度噂を知った生徒は、その後のグループワークでずっと「噂を知っている状態」であり続けます。
2. 時系列の遵守: グループワークは「予定された順番通り」に行われます。ある時点で噂を知らない生徒でも、その後のグループワークで噂を知っている生徒とペアになれば、それ以降は噂を広める側に回ります。
3. 効率的な管理: 生徒の数 \(N\) とグループワークの回数 \(M\) は最大で \(2 \times 10^5\) と大きいため、各ステップを効率よく処理する必要があります。

素朴に「各グループワークごとに全員の状態を確認する」ような処理をしてしまうと、計算時間がかかりすぎてしまいます（\(O(N \times M)\)）。しかし、各グループワークで影響を受けるのはペアを組んだ2人のみであるため、その2人の状態だけを確認・更新すれば十分です。

アルゴリズム

以下の手順でシミュレーションを行います。

1. 初期化: 長さ \(N+1\) の真偽値（Boolean）の配列 knows を用意し、すべて False（知らない）で初期化します。
2. 最初の伝達: 出席番号 \(1\) から \(K\) までの生徒に対応する knows[1] から knows[K] を True（知っている）に変更します。
3. シミュレーション: \(M\) 回のグループワークを順番に処理します。各ペア \((A_i, B_i)\) について：
   • もし knows[A_i] または knows[B_i] が True ならば、knows[A_i] と knows[B_i] の両方を True に更新します。
   • どちらも False ならば、何も変化しません。
4. 集計: 最後に knows 配列の中で True になっている要素の数を数えて出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • 配列の初期化に \(O(N)\)、グループワークの処理に \(O(M)\)、最後の集計に \(O(N)\) かかります。\(N, M \le 2 \times 10^5\) なので、制限時間内に十分間に合います。
• 空間計算量: \(O(N + M)\)
  • 生徒の状態を保存する配列に \(O(N)\)、入力を保持するリストに \(O(M)\) のメモリを使用します。

実装のポイント

• 高速な入力処理: \(M\) が大きいため、Pythonでは input() を繰り返すよりも sys.stdin.read().split() などで一括して入力を読み込む方が高速です。

• 真偽値の合計: Pythonでは True は 1、False は 0 として扱われるため、sum(knows) とするだけで噂を知っている人数を効率よくカウントできます。

• 短絡評価: if knows[u] or knows[v]: という条件式では、knows[u] が True であれば knows[v] の確認をスキップするため、わずかに効率的です。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白（スペース、改行など）で分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 読み込んだ文字列のリストを一括で整数のリストに変換します
    # これにより、個別に int() を呼び出すよりも高速に処理できます
    data = list(map(int, input_data))
    
    # N: 生徒の人数, M: グループワークの回数, K: 最初に噂を知っている生徒の人数
    N = data[0]
    M = data[1]
    K = data[2]
    
    # 各生徒が噂を知っているかどうかを保持するリスト（出席番号が 1 から N なので、サイズ N+1 で作成）
    # 初期状態は全員 False (知らない)
    knows = [False] * (N + 1)
    
    # 最初の K 人（出席番号 1 から K）に噂を伝えます
    # スライスを用いることで、ループを回すよりも効率的に初期化できます
    if K > 0:
        knows[1:K+1] = [True] * K
        
    # 各グループワークを順番にシミュレーションします
    # 各ペア (A_i, B_i) は data[3] 以降に 2 つずつ並んでいます
    for i in range(M):
        u = data[3 + 2 * i]
        v = data[4 + 2 * i]
        
        # ペアを組んだ生徒のうち、少なくとも一方が噂を知っていれば、両方が噂を知っている状態になります
        # Python の 'or' は短絡評価を行うため、knows[u] が True なら knows[v] の確認をスキップします
        if knows[u] or knows[v]:
            knows[u] = True
            knows[v] = True
            
    # 全てのグループワーク終了後、噂を知っている生徒の人数をカウントします
    # sum() 関数をブール値のリストに適用すると、True を 1, False を 0 として合計します
    print(sum(knows))

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-thinking によって生成されました。