Overview

This problem asks us to determine how many students will ultimately receive information when it spreads among students connected by friendships.

Analysis

In this problem, students are divided into groups (connected components) based on friendships. Information spreads within the same group through friendships, but does not spread to different groups.

Therefore, the answer is the sum of the sizes (number of people) of the groups to which the students who initially received the information belong.

A naive approach would be to simulate the information spread using breadth-first search or depth-first search. However, since \(N\) and \(M\) can be up to \(2 \times 10^5\), a full search would be too slow, and even an \(O(N + M)\) solution might not pass due to constant factor issues.

Thus, it is appropriate to use Union-Find (Disjoint Set Union data structure) to efficiently group students by friendships. Using Union-Find allows us to quickly perform operations for grouping friendships and checking which group a student belongs to.

Algorithm

1. Using Union-Find, divide students into connected components (groups) based on friendships.
2. Identify the groups (roots) to which the students who initially received the information belong.
3. Calculate the sum of the number of students in those groups.

Specifically: - For each friendship \((u, v)\), call union(u, v) to merge them into the same group. - For each student \(S_i\) who initially has the information, find the root of their group using find(S_i), and record it while avoiding duplicates. - Sum up the sizes of the groups corresponding to each root to get the answer.

For example, given the following input:

5 3 2
1 3
1 2
2 3
4 5

Due to friendships, students 1, 2, 3 form one group, and 4, 5 form another group. Since information is initially given to students 1 and 3, the answer is the size of that one group (3 people).

Complexity

• Time complexity: \(O(N + M \cdot \alpha(N) + K \cdot \alpha(N))\)
  (where \(\alpha(N)\) is the inverse Ackermann function, which can be considered effectively constant)
• Space complexity: \(O(N)\)

Implementation Notes

• Union-Find operates very efficiently when using path compression and merge optimization by rank/size.

• By maintaining the size at each root, we can immediately retrieve the size of each connected component.

• Since students who initially receive information may belong to the same group, we need to use a set to eliminate duplicates.

  Source Code

import sys
from collections import deque

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    
    S = list(map(int, data[3:3+K]))
    
    # Union-Find initialization
    parent = list(range(N + 1))
    size = [1] * (N + 1)
    
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])  # Path compression
        return parent[x]
    
    def union(x, y):
        root_x = find(x)
        root_y = find(y)
        if root_x != root_y:
            # Union by size
            if size[root_x] < size[root_y]:
                root_x, root_y = root_y, root_x
            parent[root_y] = root_x
            size[root_x] += size[root_y]
    
    # Process friendships
    idx = 3 + K
    for _ in range(M):
        u = int(data[idx])
        v = int(data[idx + 1])
        idx += 2
        union(u, v)
    
    # Count unique root components that contain initial informants
    informed_roots = set()
    for s in S:
        informed_roots.add(find(s))
    
    # Sum sizes of those components
    total = sum(size[root] for root in informed_roots)
    print(total)

if __name__ == "__main__":
    main()

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