Overview

This is a problem where we form groups based on friendship relations among students and determine how many people each message reaches.

Analysis

Friendships are bidirectional, and if friends are connected, they belong to the same group (connected component). In other words, if a message reaches one person, it reaches everyone in that group.

Therefore, if we know the “group size” that each student belongs to, we can answer each query by simply outputting that value.

A naive approach would be to check the connected component using BFS or DFS for each query, but in the worst case this becomes \(O(Q \cdot (N + M))\), which will result in TLE given the large constraints.

To solve this, we preprocess the “size of the group each student belongs to” for all students in advance. This allows us to respond to each query in \(O(1)\).

Algorithm

1. Graph Construction
   Build an undirected graph using an adjacency list, with students as vertices and friendships as edges.

2. Connected Component Search and Group Size Recording
   For each unvisited vertex, perform BFS or DFS from it to explore the entire connected component (group).
   During the search, determine the members and their count (count), then set group_size for all vertices belonging to that group.

3. Query Processing
   For each query, output the group_size of the specified student.

Example

For instance, consider the following input:

5 3
1 2
2 3
4 5
2
1
4

The friendships form the following groups: - Group 1: {1, 2, 3} → Size 3 - Group 2: {4, 5} → Size 2

Query 1: Message sent to student 1 → Group size is 3
Query 2: Message sent to student 4 → Group size is 2

Output:

3
2

Complexity

• Time complexity: \(O(N + M + Q)\)
• Space complexity: \(O(N + M)\)

Implementation Notes

• Since the graph is 1-indexed, array sizes should be \(N+1\).

• Use a visited flag to avoid processing a vertex that has already been explored.

• Record members during BFS, and afterwards set group_size for each member.

• sys.stdin.read is used for fast input reading.

  Source Code

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()

---

This editorial was generated by qwen3-coder-480b.