Overview

This problem asks us to find the total number of students who belong to the same connected components as the initial set of students \(S\) who first learned the information, in an undirected graph where edges represent friendship relations.

Analysis

Since information will always propagate to students who are “directly or indirectly connected through friendships,” the range where information reaches = the entire connected components to which the initially informed students belong.

For example, when the graph is divided into several connected components (groups), if even one initial member is included in a component, the information reaches everyone in that component. Conversely, information never reaches components that contain no initial members.

A naive approach would be: - Run BFS/DFS from each initial student \(s \in S\) and count all reachable vertices

However, if there are many initial students, we may end up exploring the same component multiple times, leading to a worst case of \(O(K(N+M))\), which is too slow (since \(N,M \le 2\times 10^5\), this is prohibitive).

Instead, we use Union-Find (Disjoint Set Union, DSU), which efficiently handles “connected components” of a graph: 1. First, build connected components using all edges 2. Mark the components that contain initial students 3. Sum up the sizes of the marked components

This avoids redundant exploration and solves the problem efficiently.

Algorithm

We perform the following using Union-Find:

1. Initialize Union-Find
   Each vertex starts in its own set. We use an array parent, where for roots we store parent[root] = -size (the negative of the set size).

2. Union all friendship relations
   For each edge \((u_i, v_i)\), perform union(u_i, v_i) to merge them into the same connected component.
   (We use union-by-size, where the larger set becomes the root, combined with path compression)

3. Mark the connected components that contain initial students
   For each \(s \in S\), find the root find(s) and set has[root] = True.
   This allows us to determine “this component contains an initial student.”

4. Sum the sizes of marked components for the answer
   Iterate from 1 to \(N\), and if a vertex is a root (parent[i] < 0) and has[i] == True, add the component size -parent[i] to the answer.

Complexity

• Time complexity: \(O((N+M)\alpha(N))\)
  (The find/union operations of Union-Find have an amortized nearly constant cost of \(\alpha(N)\))
• Space complexity: \(O(N)\)
  (For parent, has, etc.)

Implementation Notes

• Using an implementation where the root stores the size as a negative value in Union-Find is convenient, as the component size can be immediately retrieved as -parent[root].

• It is important to always mark the root as in has[find(s)] = True (marking intermediate nodes would break the component identification).

• Since the input can be on the scale of up to \(2\times 10^5\) lines, reading it all at once with sys.stdin.buffer.read() is faster.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)
    K = next(it)

    S = [next(it) for _ in range(K)]

    parent = [-1] * (N + 1)

    def find(x):
        while parent[x] >= 0:
            if parent[parent[x]] >= 0:
                parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a, b):
        a = find(a)
        b = find(b)
        if a == b:
            return
        if parent[a] > parent[b]:  # size(a) < size(b)
            a, b = b, a
        parent[a] += parent[b]
        parent[b] = a

    for _ in range(M):
        u = next(it)
        v = next(it)
        union(u, v)

    has = [False] * (N + 1)
    for s in S:
        has[find(s)] = True

    ans = 0
    for i in range(1, N + 1):
        if parent[i] < 0 and has[i]:
            ans += -parent[i]

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.