Overview

By treating friend relationships as a graph and precomputing the number of people in the “connected component (group)” each student belongs to, we can quickly answer the number of people reached by each notification.

Approach

• If we consider students as vertices and friend relationships as undirected edges, “students connected directly or indirectly” belong to the same connected component (group).
• When a teacher contacts student \(S_k\), everyone in that connected component receives the message, so the answer is:
  • The size of the connected component that \(S_k\) belongs to

Why a Naive Approach Doesn’t Work

If we run BFS/DFS from \(S_k\) for each query to count the number of reachable people, it costs \(O(N+M)\) in the worst case each time.
Since there are \(Q\) queries, the total becomes \(O(Q(N+M))\), which will definitely not be fast enough under the constraints (up to \(2\times 10^5\)).

Solution

Since connected components do not change across queries: 1. First, explore the entire graph once to find all connected components, recording the component ID and component size for each vertex. 2. For each query, simply “look up the component size.”

(Example)
If vertices 1–3 are connected, vertices 4–5 are connected, and vertex 6 is isolated, the component sizes are \(3, 2, 1\) respectively.
The answer for \(S_k=2\) is \(3\), and the answer for \(S_k=5\) is \(2\), which can be determined immediately.

Algorithm

1. Build an undirected graph using an adjacency list.
2. Prepare an array comp[v] to manage which connected component each vertex belongs to (component ID). Unvisited vertices are marked as -1.
3. Iterate from \(1\) to \(N\), and for each unvisited vertex, perform DFS using a stack (or BFS):
   • Assign the same component ID to all vertices in the same component
   • Count the number of vertices cnt in that component
4. Store the component size as comp_size[component ID] = cnt.
5. For each query \(S_k\), output comp_size[comp[S_k]].

Complexity

• Time complexity: \(O(N+M+Q)\)
  (Connected component exploration takes \(O(N+M)\), and each query is just a lookup in \(O(1)\))
• Space complexity: \(O(N+M)\)
  (Adjacency list, component information, stack, etc.)

Implementation Notes

• Instead of recursive DFS, iterative DFS with a stack is used (because in Python, deep recursion may cause a crash due to the recursion limit).

• Since the input can be up to \(2\times 10^5\) in scale, fast input using sys.stdin.buffer.read() is employed.

• comp is made 1-indexed (size \(N+1\)) to align with the problem’s student numbering, simplifying the implementation.

  Source Code

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

This editorial was generated by gpt-5.2-high.