Overview

This problem asks us to simulate the spread of a rumor through a friendship network, where the rumor propagates to a student only when the number of their acquaintances who know the rumor reaches a threshold \(T\) or more, and to determine the final number of students who know the rumor.

Analysis

The rumor propagation process proceeds as follows: each day, among the students who do not yet know the rumor, those whose number of friends who know the rumor has reached \(T\) or more all learn the rumor simultaneously. A naive approach (checking all students every day) would require up to \(N\) iterations, and checking \(N\) students each day results in \(O(N^2)\) time complexity. Since \(N\) can be up to \(2 \times 10^5\), this would not meet the time limit.

An efficient solution uses a BFS-like approach with a queue. However, unlike standard BFS, the key difference is that each vertex (student) counts the number of “friends who know the rumor,” and is added to the queue only when that count reaches the threshold \(T\).

Algorithm

1. Graph Construction: Represent the friendship relations between students as an undirected graph using an adjacency list.
2. Initialization: Add the students who initially know the rumor to the queue and mark them in the knows array.
3. Propagation Simulation:
   • Dequeue a student and process all of their friends (adjacent vertices).
   • For each friend, if they do not yet know the rumor, increment their “number of friends who know the rumor” (informed_neighbors) by 1.
   • If this count reaches the threshold \(T\) or more, mark that student as knowing the rumor and add them to the queue.
4. Result Calculation: Count the number of students whose knows array entry is True.

In this approach, each edge (friendship) is processed at most twice (once for each direction), allowing the propagation to be simulated efficiently.

Complexity

• Time complexity: \(O(N + M)\)
  • Graph construction takes \(O(N + M)\)
  • The BFS-like processing handles each vertex and each edge a constant number of times, so \(O(N + M)\)
• Space complexity: \(O(N + M)\)
  • The graph adjacency list requires \(O(N + M)\)
  • The knows and informed_neighbors arrays require \(O(N)\)

Implementation Notes

• Since the graph is undirected, edges must be added in both directions.

• Only students who “newly learn” the rumor are added to the queue (students who already know it are not added).

• The informed_neighbors array, which tracks the number of friends who know the rumor for each student, is crucial. It allows us to precisely detect the moment when the threshold \(T\) is exceeded.

• Since the input values can be large, using sys.stdin.read for bulk input reading speeds up the input processing.

  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

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

    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)

    degree = [len(adj[i]) for i in range(N + 1)]
    informed_neighbors = [0] * (N + 1)
    knows = [False] * (N + 1)
    
    queue = deque()
    for c in initial:
        knows[c] = True
        queue.append(c)
    
    while queue:
        current = queue.popleft()
        for neighbor in adj[current]:
            if knows[neighbor]:
                continue
            informed_neighbors[neighbor] += 1
            if informed_neighbors[neighbor] >= T:
                knows[neighbor] = True
                queue.append(neighbor)

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

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.