Overview

This problem involves representing friendships as a graph and finding the total number of students reachable from the students who initially received the information. This is a classic graph traversal problem involving connected components.

Analysis

Problem Reformulation

Consider a graph where students are vertices and friendships are edges. The condition “information will definitely reach students who are directly or indirectly connected through friendships” means that all students belonging to the same connected component will receive the information.

Understanding Through a Concrete Example

For example, suppose there are 5 students with the following friendships: - 1-2, 2-3 (students 1, 2, 3 are connected) - 4-5 (students 4, 5 are connected)

If information is initially given to student 1: - The information spreads: student 1 → student 2 → student 3 - Students 4 and 5 do not receive it (because they are in a different connected component)

Result: 3 students receive the information

Choosing an Approach

• Naive method: For each student, check one by one whether they are in the same connected component as the students who initially received the information → Inefficient
• Efficient method: Use all students who initially received the information as starting points, and find all reachable students in a single traversal → BFS/DFS in \(O(N+M)\)

Algorithm

We use Breadth-First Search (BFS).

1. Graph Construction: Represent friendships using an adjacency list
2. Initialization: Add all \(K\) students who initially received the information to the queue and mark them as visited
3. BFS Execution: Remove a student from the queue, add their unvisited friends to the queue, and mark them as visited
4. Counting: The number of visited students is the answer

Initial state: Queue = [S₁, S₂, ..., Sₖ] (students who initially received the information)
         
Repeat:
  Remove a student from the queue
  Add their unvisited friends to the queue
  
Termination condition: Queue becomes empty

By performing BFS simultaneously from multiple starting points, we can efficiently find all students connected to the students who initially received the information.

Complexity

• Time Complexity: \(O(N + M)\)

  • Graph construction takes \(O(M)\)
  • BFS visits each vertex at most once and each edge at most twice (both directions), so \(O(N + M)\)

• Space Complexity: \(O(N + M)\)

  • Adjacency list uses \(O(N + M)\)
  • Visited array uses \(O(N)\)
  • Queue uses at most \(O(N)\)

Implementation Notes

1. Handling Vertex Numbers: Since the problem uses student numbers starting from 1, it’s convenient to set the array size to \(N+1\) and use 1-indexed arrays

2. Multi-source BFS: By adding all K students to the queue initially, the algorithm correctly handles cases where they span multiple connected components

3. Preventing Duplicate Visits: Using a visited array and marking students as visited when adding them to the queue prevents processing the same student multiple times

4. Fast Input: Since \(N, M\) can be as large as \(2 \times 10^5\), we use sys.stdin.readline to speed up input

Source Code

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    S = list(map(int, input().split()))
    
    # Build adjacency list
    adj = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v = map(int, input().split())
        adj[u].append(v)
        adj[v].append(u)
    
    # Count students who receive information using BFS
    visited = [False] * (N + 1)
    queue = deque()
    
    # Add students who initially received information to the queue
    for s in S:
        if not visited[s]:
            visited[s] = True
            queue.append(s)
    
    # BFS
    while queue:
        current = queue.popleft()
        for neighbor in adj[current]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)
    
    # Count the number of students who received information
    count = sum(visited)
    print(count)

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.