概要

友人関係をグラフとして表現し、最初に情報を伝えた生徒から到達可能な全ての生徒の人数を求める問題です。これはグラフの連結成分に関する典型的な探索問題です。

考察

問題の言い換え

友人関係を辺、生徒を頂点とするグラフを考えます。「友人関係で直接または間接的につながっている生徒には必ず情報が伝わる」という条件は、同じ連結成分に属する生徒全員に情報が届くことを意味します。

具体例で理解する

例えば、5人の生徒がいて以下の友人関係があるとします： - 1-2, 2-3（生徒1,2,3が連結） - 4-5（生徒4,5が連結）

最初に生徒1に情報を伝えた場合： - 生徒1 → 生徒2 → 生徒3 と情報が伝わる - 生徒4, 5には届かない（別の連結成分のため）

結果：3人に情報が届く

アプローチの選択

• 素朴な方法: 各生徒について、最初に情報を伝えた生徒と同じ連結成分にいるか一つ一つ判定する → 非効率
• 効率的な方法: 最初に情報を伝えた生徒全員を出発点として、到達可能な生徒を一度の探索で全て見つける → BFS/DFSで \(O(N+M)\)

アルゴリズム

幅優先探索（BFS） を使用します。

1. グラフの構築: 友人関係を隣接リストで表現する
2. 初期化: 最初に情報を伝えた \(K\) 人の生徒を全てキューに入れ、訪問済みとしてマークする
3. BFS実行: キューから生徒を取り出し、その友人でまだ訪問していない生徒をキューに追加し訪問済みにする
4. カウント: 訪問済みの生徒数が答え

初期状態: キュー = [S₁, S₂, ..., Sₖ]（最初に情報を伝えた生徒）
         
繰り返し:
  キューから生徒を取り出す
  その生徒の友人で未訪問の人をキューに追加
  
終了条件: キューが空になる

複数の出発点から同時にBFSを行うことで、最初に情報を伝えた生徒と連結している全ての生徒を効率的に見つけられます。

計算量

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

  • グラフの構築に \(O(M)\)
  • BFSで各頂点を高々1回、各辺を高々2回（両方向）訪問するため \(O(N + M)\)

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

  • 隣接リストに \(O(N + M)\)
  • 訪問済み配列に \(O(N)\)
  • キューに最大 \(O(N)\)

実装のポイント

1. 頂点番号の扱い: 問題では生徒番号が1から始まるため、配列サイズを \(N+1\) にして1-indexedで扱うと便利

2. 複数始点のBFS: 最初にK人全員をキューに入れることで、複数の連結成分にまたがっていても正しく処理できる

3. 重複訪問の防止: visited配列を使い、キューに追加する際に訪問済みマークをつけることで、同じ生徒を複数回処理することを防ぐ

4. 高速な入力: \(N, M\) が最大 \(2 \times 10^5\) と大きいため、sys.stdin.readline を使って入力を高速化している

   ソースコード

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    S = list(map(int, input().split()))
    
    # 隣接リストを構築
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v = map(int, input().split())
        adj[u].append(v)
        adj[v].append(u)
    
    # BFSで情報が届く生徒を数える
    visited = [False] * (N + 1)
    queue = deque()
    
    # 最初に情報を伝えた生徒をキューに追加
    for s in S:
        if not visited[s]:
            visited[s] = True
            queue.append(s)
    
    # BFS
    while queue:
        current = queue.popleft()
        for neighbor in adj[current]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)
    
    # 情報が届いた生徒の数をカウント
    count = sum(visited)
    print(count)

if __name__ == "__main__":
    main()

---

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