Overview

Rumors spread through friendships, and each day, uninfected students who have “\(T\) or more friends who know the rumor” newly learn the rumor. Simulate this process and find the total number of students who ultimately know the rumor.

Analysis

This problem is a simulation problem where information propagates on a graph.

• Consider an undirected graph where each student is a vertex and friendships are edges.
• The initially informed students are given, and from there, the rumor spreads according to the rule: “if \(T\) or more of a person’s adjacent vertices already know the rumor, that person also learns it.”
• Since this propagation happens simultaneously, it is natural to process it in a BFS-like manner.

A naive approach of “checking the condition for every student each day” would take up to \(N\) days, with \(O(N)\) work each day, resulting in \(O(N^2)\) overall. Since the constraint is \(N \leq 2 \times 10^5\), this would TLE.

The key insight is to maintain a counter for each vertex tracking “the number of friends who know the rumor.” We increment the count for adjacent vertices of the initially informed students, and when the count reaches \(T\), we add that vertex to the queue. This allows for an efficient simulation.

Algorithm

1. Represent the graph as an adjacency list.
2. knows[i]: A flag indicating whether student \(i\) knows the rumor.
3. informed_neighbors[i]: The number of friends of student \(i\) who already know the rumor.
4. For uninfected students adjacent to the initial \(K\) informed students, increment informed_neighbors. If it reaches \(T\) or more, add them to the queue.
5. Dequeue a student, mark them as knowing the rumor, then increment informed_neighbors for their adjacent uninfected students. If any reach \(T\), add them to the queue.
6. When the queue is empty, terminate. Output the number of students for whom knows is True.

Complexity

• Time complexity: \(O(N + M)\)
  Each vertex and edge is processed only a constant number of times.
• Space complexity: \(O(N + M)\)
  For the adjacency list of the graph and various arrays.

Implementation Notes

• Use a knows array to track students who already know the rumor. When dequeuing a student who already knows the rumor, skip them to prevent double counting.

• The initial state of the queue should contain only those adjacent vertices of the initially informed students whose informed_neighbors count has reached \(T\) or more.

• 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
    K = int(data[idx]); idx += 1
    T = int(data[idx]); idx += 1

    knows = [False] * (N + 1)
    initial = []
    for _ in range(K):
        c = int(data[idx]); idx += 1
        initial.append(c)
        knows[c] = True

    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)

    # Count how many informed neighbors each node has
    informed_neighbors = [0] * (N + 1)
    queue = deque()

    # Initialize counts and queue based on initial knowers
    for c in initial:
        for neighbor in adj[c]:
            if not knows[neighbor]:
                informed_neighbors[neighbor] += 1
                if informed_neighbors[neighbor] >= T:
                    queue.append(neighbor)

    # Propagate the rumor
    while queue:
        current = queue.popleft()
        if knows[current]:
            continue
        knows[current] = True
        for neighbor in adj[current]:
            if not knows[neighbor]:
                informed_neighbors[neighbor] += 1
                if informed_neighbors[neighbor] >= T:
                    queue.append(neighbor)

    result = sum(knows[1:])
    print(result)

if __name__ == "__main__":
    main()

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