Overview

This is a simulation problem where rumors gradually spread on a graph. Starting from \(K\) people who initially know the rumor, the rumor propagates to students who have “\(T\) or more friends who know the rumor,” and we need to find the total number of students who know the rumor in the end.

Analysis

Naive Approach and Its Issues

The simplest method is to “simulate one day at a time.” Each day, scan all students, and for each student who doesn’t know the rumor, count “how many of their friends know the rumor.” If the count is \(T\) or more, they newly learn the rumor. Repeat this process.

However, in the worst case, only one person may newly learn the rumor per day, and scanning all students and edges each day results in \(O(N \times (N + M))\), which causes TLE when \(N, M\) are \(2 \times 10^5\).

Key Insight: BFS-like Propagation

The spread of rumors has a structure similar to BFS (Breadth-First Search).

• For each student, maintain a counter friend_count tracking “the number of friends who know the rumor”
• At the exact moment the counter reaches \(T\), add the student to the queue
• Students dequeued learn the rumor, and their friends’ counters are updated

This way, each edge is processed at most once, enabling efficient simulation.

Concrete Example

For example, with \(N=5, T=2\), where students 1 and 2 initially know the rumor, and edges are \((1,3), (2,3), (3,4), (4,5)\):

1. Initial state: Students 1, 2 know the rumor. Student 3’s friend_count is 2 (friends 1 and 2 know it) → reaches the threshold \(T=2\), so it’s added to the queue
2. Student 3 learns the rumor: Student 4’s friend_count increases to 1 → still less than \(T=2\), so it’s not added to the queue
3. Termination: The queue becomes empty, and the students who ultimately know the rumor are students 1, 2, 3 — 3 people

Algorithm

1. Build an adjacency list adj
2. For the students who initially know the rumor, set knows[c] = True
3. For each initial rumor-knowing student \(c\), increment friend_count[nb] by 1 for each friend \(nb\). If friend_count[nb] becomes exactly \(T\), add \(nb\) to the queue
4. Dequeue a student node, and if they don’t know the rumor yet and friend_count[node] >= T:
   • Set knows[node] = True
   • For each friend \(nb\) of node, increment friend_count[nb] by 1, and if it reaches exactly \(T\), add it to the queue
5. When the queue is empty, count and output the number of students where knows is True

Complexity

• Time complexity: \(O(N + M)\)
  • Each student enters the queue at most once, and each edge is processed at most twice (once from each endpoint)
• Space complexity: \(O(N + M)\)
  • Used for the adjacency list, counter array, queue, etc.

Implementation Notes

• Timing of queue insertion: Add to the queue only at the exact moment friend_count reaches \(T\). This prevents the same student from being added to the queue multiple times, maintaining efficiency

• Check when dequeuing: As a safeguard against duplicate queue entries, skip if knows[node] is already True

• Correctness of simultaneous propagation: The problem states that “all new transmissions occur simultaneously,” but the BFS approach of adding to the queue when the counter reaches the threshold produces the same result. This is because whether a student learns the rumor depends on “the final number of friends who know the rumor,” which is independent of the propagation order

  Source Code

import sys
from collections import deque

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    T = int(input_data[idx]); idx += 1
    
    knows = [False] * (N + 1)
    initial = []
    for i in range(K):
        c = int(input_data[idx]); idx += 1
        initial.append(c)
        knows[c] = True
    
    adj = [[] for _ in range(N + 1)]
    for i in range(M):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        adj[u].append(v)
        adj[v].append(u)
    
    # count of friends who know the rumor
    friend_count = [0] * (N + 1)
    
    queue = deque()
    
    # Initialize: for each initial knower, update their friends' counts
    for c in initial:
        for nb in adj[c]:
            if not knows[nb]:
                friend_count[nb] += 1
                if friend_count[nb] == T:
                    queue.append(nb)
    
    while queue:
        node = queue.popleft()
        if knows[node]:
            continue
        # Check if still meets threshold (it should since we only enqueue at threshold)
        if friend_count[node] >= T:
            knows[node] = True
            for nb in adj[node]:
                if not knows[nb]:
                    friend_count[nb] += 1
                    if friend_count[nb] == T:
                        queue.append(nb)
    
    print(sum(knows[1:N+1]))

main()

---

This editorial was generated by claude4.6opus-thinking.