概要

生徒の友達関係からなるグループを構成し、各連絡が届く人数を求める問題です。

考察

友達関係は双方向であり、友達同士がつながっていれば同じグループ（連結成分）に属します。つまり、一人に連絡がいけば、そのグループ全員に連絡が届きます。

したがって、各生徒が所属する「グループの大きさ」が分かれば、各クエリに対してその値を出力するだけで答えが得られます。

素朴な方法として、毎回BFSやDFSで連結成分を調べる方法がありますが、最悪ケースで \(O(Q \cdot (N + M))\) となり、制約が大きいのでTLEになります。

これを解決するために、事前に全生徒について「所属するグループのサイズ」を前処理して求めることにします。これにより、クエリへの応答は \(O(1)\) で行えます。

アルゴリズム

1. グラフ構築
   生徒を頂点、友達関係を辺とする無向グラフを隣接リストで構築します。

2. 連結成分の探索とグループサイズの記録
   未訪問の頂点があれば、そこからBFSまたはDFSを行い、連結成分（グループ）全体を探索します。
   探索中に所属するメンバーとその人数（count）を求め、そのグループに属する全頂点に group_size を設定します。

3. クエリ処理
   各クエリに対し、指定された生徒の group_size を出力します。

例

例えば、以下のような入力があったとします：

5 3
1 2
2 3
4 5
2
1
4

友達関係によって以下のようなグループができます： - グループ1: {1, 2, 3} → サイズ3 - グループ2: {4, 5} → サイズ2

クエリ1：生徒1に連絡 → グループサイズは3
クエリ2：生徒4に連絡 → グループサイズは2

出力：

3
2

計算量

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

実装のポイント

• グラフは1-indexedで扱うため、配列のサイズは \(N+1\) にする。

• visited フラグを使って、一度調べた頂点を再度処理しないようにする。

• BFS内で members を記録しておき、後で各メンバーに group_size をセットする。

• 入力を高速に読み込むために sys.stdin.read を使用している。

  ソースコード

import sys
from collections import deque

def main():
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    # 隣接リストの構築 (1-indexed)
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        u = int(data[idx])
        idx += 1
        v = int(data[idx])
        idx += 1
        adj[u].append(v)
        adj[v].append(u)
    
    # 各ノードの所属するグループサイズを記録
    group_size = [0] * (N+1)
    visited = [False] * (N+1)
    
    for i in range(1, N+1):
        if not visited[i]:
            # BFSで連結成分を探索
            queue = deque([i])
            visited[i] = True
            members = [i]
            count = 1
            
            while queue:
                u = queue.popleft()
                for v in adj[u]:
                    if not visited[v]:
                        visited[v] = True
                        queue.append(v)
                        members.append(v)
                        count += 1
            
            # 連結成分内の全メンバーにグループサイズを設定
            for member in members:
                group_size[member] = count
    
    Q = int(data[idx])
    idx += 1
    result = []
    for _ in range(Q):
        s = int(data[idx])
        idx += 1
        result.append(str(group_size[s]))
    
    print('\n'.join(result))

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。