概要

この問題は、グラフ理論における「連結成分」のサイズを求める問題です。友達関係を辺、生徒を頂点としたグラフを考え、各クエリで指定された生徒が属する連結成分（グループ）に何人の生徒が含まれているかを答えます。

考察

問題の言い換え

「友達関係で直接または間接的に繋がっている」という条件は、グラフ理論における連結成分を指します。先生がある生徒に連絡したとき、その連絡はその生徒が属するグループの全員に伝わります。したがって、求めるべき値は「生徒 \(S_k\) が属する連結成分の頂点数」です。

素朴なアプローチとその限界

各クエリ \(Q\) に対して、その都度グラフを探索（BFSやDFS）してグループの人数を数えると、最悪の場合 \(O(Q \times (N + M))\) の時間がかかります。制約では \(N, M, Q\) がすべて \(2 \times 10^5\) であるため、これでは間に合いません。

効率的な解決策

事前にすべてのグループを特定し、それぞれのグループの人数を計算しておくことで、各クエリに対して \(O(1)\) で回答できるようになります。 1. グラフを構築する。 2. まだ探索していない生徒を起点として、BFS（幅優先探索）やDFS（深さ優先探索）を行い、同じグループに属する生徒をすべて洗い出す。 3. そのグループの人数を記録し、グループ内の全生徒にその人数を紐付ける。 4. すべての生徒について探索が終わるまで繰り返す。

アルゴリズム

1. グラフの構築

生徒を頂点、友達関係を無向辺としてグラフを構築します。Pythonでは通常 list の list で隣接リストを作りますが、メモリ効率や速度のために、提示されたコードでは CSR (Compressed Sparse Row) 形式のようなフラットな配列による表現を用いています。

2. 連結成分の探索 (BFS)

未訪問の頂点から BFS を開始します。 - キュー（探索待ちリスト）を用いて、繋がっている頂点を次々と訪問します。 - 1回の BFS で訪問できた頂点の集合が1つのグループです。 - そのグループの要素数（len(component_queue)）を記録し、グループに属するすべての生徒の回答用配列（res_sizes）にその値を格納します。

3. クエリへの回答

各クエリ \(S_k\) に対して、あらかじめ計算しておいた res_sizes[S_k] を出力します。

計算量

• 時間計算量: \(O(N + M + Q)\)
  • グラフの構築に \(O(N + M)\)
  • BFS による全頂点の探索に \(O(N + M)\)（各頂点と各辺を定数回ずつ走査するため）
  • \(Q\) 個のクエリへの回答に \(O(Q)\)
• 空間計算量: \(O(N + M)\)
  • 隣接リストの保持に \(O(N + M)\)
  • 訪問済みフラグやグループサイズ情報の保持に \(O(N)\)

実装のポイント

• 高速な入出力: Pythonで \(10^5\) を超える入力を扱う場合、input() を繰り返すよりも sys.stdin.read().split() で一括で読み込み、sys.stdout.write() で一括で出力する方が大幅に高速です。

• グラフ表現: adj = [[] for _ in range(N)] のようなリストのリストは直感的ですが、Pythonではオーバーヘッドが大きくなることがあります。提示されたコードのように、1次元配列とオフセット（offsets）を組み合わせる手法は、メモリ節約と高速化に有効です。

• 再帰制限: DFS を使う場合は sys.setrecursionlimit で再帰深さを増やす必要がありますが、BFS を使えばその心配はありません。

  ソースコード

import sys

def solve():
    # Fast I/O: Read all input at once and convert to a list of integers
    # This approach is generally faster in Python than multiple input() or sys.stdin.readline() calls.
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Map all string tokens to integers
    data = list(map(int, input_data))
    
    N = data[0]
    M = data[1]
    
    # Build the graph using Compressed Sparse Row (CSR) format.
    # This representation is memory-efficient and avoids the overhead of a list of lists.
    
    # Step 1: Count the degree of each node (student)
    degree = [0] * (N + 1)
    for i in range(M):
        u = data[2 + 2 * i]
        v = data[3 + 2 * i]
        degree[u] += 1
        degree[v] += 1
        
    # Step 2: Calculate the starting offsets for each student's adjacency list in a flat array
    # offsets[u-1] will be the start index of student u's neighbors in the 'adj' array.
    offsets = [0] * (N + 1)
    for i in range(N):
        offsets[i + 1] = offsets[i] + degree[i + 1]
        
    # Step 3: Populate the flat adjacency array
    adj = [0] * offsets[N]
    # Use a temporary pointer array to keep track of the next insertion position for each student
    curr_pos = list(offsets)
    for i in range(M):
        u = data[2 + 2 * i]
        v = data[3 + 2 * i]
        # Store neighbor v in u's slice
        adj[curr_pos[u - 1]] = v
        curr_pos[u - 1] += 1
        # Store neighbor u in v's slice
        adj[curr_pos[v - 1]] = u
        curr_pos[v - 1] += 1
        
    # Step 4: Identify connected components and calculate their sizes using BFS
    # res_sizes[i] will store the total number of students in the group containing student i.
    res_sizes = [0] * (N + 1)
    visited = [False] * (N + 1)
    
    # Identify where the query section begins in the flattened input data
    q_ptr_start = 2 + 2 * M
    Q = data[q_ptr_start]
    
    for i in range(1, N + 1):
        if not visited[i]:
            # Perform BFS to find all students in the same connected component
            component_queue = [i]
            visited[i] = True
            head = 0
            while head < len(component_queue):
                u = component_queue[head]
                head += 1
                
                # Retrieve neighbors of student u using CSR offsets
                start_idx = offsets[u - 1]
                end_idx = offsets[u]
                for j in range(start_idx, end_idx):
                    neighbor = adj[j]
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        component_queue.append(neighbor)
            
            # The length of 'component_queue' is the size of the current group
            group_size = len(component_queue)
            for student in component_queue:
                res_sizes[student] = group_size
                
    # Step 5: Answer each query based on the calculated group sizes
    output_results = []
    for i in range(Q):
        target_student = data[q_ptr_start + 1 + i]
        output_results.append(str(res_sizes[target_student]))
        
    # Output all answers joined by newlines
    sys.stdout.write('\n'.join(output_results) + '\n')

if __name__ == '__main__':
    solve()

---

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