概要

友達関係をグラフとみなし、各生徒が属する「連結成分（グループ）」の人数を前計算しておくことで、各連絡で届く人数を高速に答える問題です。

考察

• 生徒を頂点、友達関係を無向辺とすると、「直接または間接的に繋がっている生徒」は同じ連結成分（グループ）に属します。
• 先生が生徒 \(S_k\) に連絡すると、その連結成分にいる全員が連絡を受け取るので、答えは
  • \(S_k\) が属する連結成分のサイズ になります。

素朴な方法がダメな理由

各クエリごとに \(S_k\) から BFS/DFS をして到達できる人数を数えると、最悪で毎回 \(O(N+M)\) かかります。
クエリが \(Q\) 回あるので、合計 \(O(Q(N+M))\) となり、制約（最大 \(2\times 10^5\)）では確実に間に合いません。

解決策

連結成分はクエリによって変化しないので、 1. 最初にグラフ全体の連結成分を一度だけ探索して、各頂点の成分IDと成分サイズを記録 2. 各クエリは「成分サイズを参照するだけ」 にします。

（例）
1〜3が繋がり、4〜5が繋がり、6が孤立なら成分サイズはそれぞれ \(3,2,1\)。
\(S_k=2\) の答えは \(3\)、\(S_k=5\) の答えは \(2\) のように即座に分かります。

アルゴリズム

1. 隣接リストで無向グラフを構築する。
2. 配列 comp[v] を用意し、各頂点がどの連結成分に属するか（成分ID）を管理する。未訪問は -1。
3. 1 から \(N\) まで順に見て、未訪問の頂点からスタックを使って DFS（または BFS）を行い、
   • 同じ成分に属する頂点に同じ成分IDを付与
   • その成分に含まれる頂点数 cnt を数える
4. 成分サイズを comp_size[成分ID] = cnt として保存する。
5. 各クエリ \(S_k\) について、comp_size[comp[S_k]] を出力する。

計算量

• 時間計算量: \(O(N+M+Q)\)
  （連結成分の探索で \(O(N+M)\)、各クエリは参照だけで \(O(1)\)）
• 空間計算量: \(O(N+M)\)
  （隣接リスト、成分情報、スタックなど）

実装のポイント

• 再帰DFSは使わずスタックで反復DFSにしています（Python では再帰が深くなると再帰上限により落ちる可能性があるため）。

• 入力が最大 \(2\times 10^5\) 規模なので、sys.stdin.buffer.read() を使った高速入力にしています。

• comp を 1-indexed（サイズ \(N+1\)）にして、問題の生徒番号と揃えることで実装を簡単にしています。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read()
    n = len(data)
    i = 0

    def next_int():
        nonlocal i
        while i < n and data[i] <= 32:
            i += 1
        val = 0
        while i < n and data[i] > 32:
            val = val * 10 + (data[i] - 48)
            i += 1
        return val

    N = next_int()
    M = next_int()

    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = next_int()
        v = next_int()
        adj[u].append(v)
        adj[v].append(u)

    comp = [-1] * (N + 1)
    comp_size = []

    cid = 0
    for s in range(1, N + 1):
        if comp[s] != -1:
            continue
        stack = [s]
        comp[s] = cid
        cnt = 0
        while stack:
            x = stack.pop()
            cnt += 1
            for y in adj[x]:
                if comp[y] == -1:
                    comp[y] = cid
                    stack.append(y)
        comp_size.append(cnt)
        cid += 1

    Q = next_int()
    out = []
    for _ in range(Q):
        s = next_int()
        out.append(str(comp_size[comp[s]]))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

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