Overview

This is a problem where students who know a rumor spread it through group work pairs in order, and we need to determine the final number of students who know the rumor.

Analysis

Key Insight

The key point of this problem is that group work is performed in sequential order. The propagation of the rumor depends on the chronological order.

For example, consider the following case:

• \(N = 4, M = 2, K = 1\) (Student 1 initially knows the rumor)
• Group work 1: Student 2 and Student 3 are paired
• Group work 2: Student 1 and Student 2 are paired

In this case: 1. At the time of group work 1, neither Student 2 nor Student 3 knows the rumor, so nothing happens. 2. In group work 2, Student 1 (who knows the rumor) is paired with Student 2, so Student 2 learns the rumor.

Ultimately, Students 1 and 2 know the rumor — 2 people. If the order were reversed, the result would change. This illustrates why it is important that the order must not be ignored.

Approach

Since the number of group work sessions \(M\) is at most \(2 \times 10^5\), which is sufficiently small, it is enough to simply simulate each group work session one by one in order.

For each group work session, if at least one of the pair knows the rumor, we update both to the state of knowing the rumor.

Algorithm

1. Prepare an array knows of length \(N+1\), and initialize students with attendance numbers \(1\) through \(K\) to True (knows the rumor).
2. Process the \(M\) group work sessions in order:
   • Read the pair \((A_i, B_i)\).
   • If either knows[A_i] or knows[B_i] is True, set both to True.
3. Finally, count the number of True values in the knows array and output it.

Concrete example (\(N=5, M=3, K=2\), i.e., Students 1 and 2 initially know the rumor):

Group Work	Pair	Students Who Know the Rumor
Initial state	-	{1, 2}
1st	(2, 4)	{1, 2, 4} (Student 2 knows, so it spreads to Student 4)
2nd	(3, 5)	{1, 2, 4} (Neither knows, so no change)
3rd	(4, 5)	{1, 2, 4, 5} (Student 4 knows, so it spreads to Student 5)

Answer: 4

Complexity

• Time complexity: \(O(N + M)\)
  • \(O(N)\) for initialization, \(O(1)\) per group work session for a total of \(O(M)\), and \(O(N)\) for the final count
• Space complexity: \(O(N)\)
  • For the knows array

Implementation Tips

• Since student attendance numbers start from \(1\), it is convenient to allocate an array of size \(N+1\) and use 1-indexed access.

• Manage the knows array with bool type, and count the number of True values using sum(knows) (in Python, True is treated as 1 and False as 0 when summed).

• Since the order of group work affects the result, it is essential to process them in the exact order they are given in the input.

  Source Code

import sys
input = sys.stdin.readline

def main():
    N, M, K = map(int, input().split())
    
    # knows[i] = True if student i knows the rumor
    knows = [False] * (N + 1)
    for i in range(1, K + 1):
        knows[i] = True
    
    for _ in range(M):
        a, b = map(int, input().split())
        if knows[a] or knows[b]:
            knows[a] = True
            knows[b] = True
    
    print(sum(knows))

main()

---

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