Overview

Given information about which student each student gave a present to, the problem asks us to count the number of students who received no presents from anyone.

Analysis

Each student gives a present to exactly one person. In other words, we can think of this as a graph with \(N\) directed edges of the form “student \(i \rightarrow T_i\)”.

In this case, the number of times student \(x\) receives a present equals the number of edges directed toward \(x\) (the in-degree).
Therefore, “students who received no presents” are vertices with in-degree \(0\).

Why the naive approach is too slow

For example, if we check whether “student \(i\) received a present from someone” by examining \(T_j\) for all students: - For each \(i\), scan \(j=1..N\) → \(O(N)\) - Doing this for all \(N\) students → total \(O(N^2)\)

Since \(N \le 2 \times 10^5\), \(O(N^2)\) is far too slow.

Solution

By scanning all \(T_i\) values just once and incrementing the count (in-degree) for the receiving side using an array, we can solve this in \(O(N)\) total.

Concrete example

When \(N=4,\ T=[2,2,4,2]\): - Student 2 receives from students 1, 2, and 4, totaling 3 times → in-degree 3 - Student 4 receives from student 3, once → in-degree 1 - Students 1 and 3 receive from no one → in-degree 0

Therefore the answer is 2 students.

Algorithm

1. Prepare an array indeg of length \(N+1\), initialized to all 0s (1-indexed).
2. For each \(i=1..N\), count the in-degree by setting indeg[T_i] += 1.
3. Count and output the number of \(i=1..N\) satisfying indeg[i] == 0.

Complexity

• Time complexity: \(O(N)\) (one pass to count \(T_i\) values, and one pass to count zeros)
• Space complexity: \(O(N)\) (in-degree array)

Implementation Notes

• For clarity with indices, make indeg have N+1 elements so that student numbers can be used directly as indices (1-indexed).

• Since the input size can be large, in Python using sys.stdin.buffer.read() is a safe way to speed up input.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N = data[0]
    T = data[1:]

    indeg = [0] * (N + 1)
    for t in T:
        indeg[t] += 1

    ans = 0
    for i in range(1, N + 1):
        if indeg[i] == 0:
            ans += 1

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.