Overview

Each firework \(i\) has a single arrow \(i \to T_i\), forming a graph with out-degree 1. When launched optimally, “exactly 1 firework per directed cycle must inevitably be destroyed”, so the answer is \(N - (\text{number of cycles})\).

Analysis

1. Viewing as a graph

When firework \(i\) is launched, if \(T_i\) is still “in preparation,” then \(T_i\) is destroyed. This corresponds to drawing a directed edge \(i \to T_i\), where:

• Launching a vertex first may make its destination (the next vertex) “unlaunchable”

Since each vertex has out-degree 1, this graph is a functional graph (each connected component consists of “one directed cycle + trees flowing into it”).

2. What happens with cycles (inevitable loss)

Example: Consider the 3-cycle \(1 \to 2 \to 3 \to 1\).

• If we launch 1 first, then 2 is destroyed
• If we launch 2 first, then 3 is destroyed
• If we launch 3 first, then 1 is destroyed

In other words, it is impossible to launch all fireworks on a cycle, and no matter the order, at least 1 firework per cycle is destroyed.

3. Non-cycle parts (trees flowing into cycles) can all be launched

If we think of edges toward the cycle (\(v \to T_v\)) as pointing “toward the parent,” then for the tree parts:

• If we launch the cycle side (parent) first
• Then when we later launch a child, \(T_v\) is “already launched,” so no destruction occurs

Thus, all tree parts can be fully launched. Ultimately, the unavoidable loss is exactly “1 per cycle”.

Therefore, the maximum number of launches is [ N - (\text{number of directed cycles}) ]

4. Why naive search for the optimal order is infeasible

There are up to \(N!\) possible orderings, and with \(N \le 10^6\), exhaustive search is impossible. However, from the observation above, instead of finding the “ordering itself,” we only need to count the number of cycles to get the answer.

Algorithm

Step 1: Remove vertices not contained in any cycle (removal from in-degree 0)

Count the in-degree (indeg) of each vertex. Vertices with in-degree 0 can never be part of a cycle, so we add them to a queue and remove them.

• Remove vertex \(v\) with in-degree 0
• Consider the edge \(v \to T_v\) as removed, and decrease the in-degree of \(T_v\) by 1
• If \(T_v\)’s in-degree becomes 0 as a result, add it as a removal candidate

This follows the same approach as Kahn’s topological sort. In a functional graph, after this process, the vertices that remain are exactly the “vertices on cycles”.

Step 2: Count the number of cycles among the remaining vertices

Looking only at the vertices that were not removed, they all lie on cycles. Following \(T\) from an unvisited remaining vertex always leads back to the starting point (discovering one cycle), so:

• When an unvisited remaining vertex is found, increment the cycle count by 1
• Mark all vertices on that cycle as visited

Repeat this to count the number of cycles.

Finally, output [ \text{answer} = N - \text{cycles} ]

Complexity

• Time complexity: \(O(N)\) (In-degree computation, removal processing, and cycle counting each process every vertex a constant number of times)
• Space complexity: \(O(N)\) (\(T\) array, in-degrees, removed/visited flags, etc.)

Implementation Notes

• Since \(N \le 10^6\), in Python using array('I') or bytearray instead of lists provides more stable memory usage and speed.

• Since input can be very large, using sys.stdin.buffer.read() with a custom parser speeds things up.

• Managing “removed” and “visited (for cycle counting)” as separate flags keeps the implementation simple.

  Source Code

import sys
from collections import deque
from array import array

def ints_from_bytes(data: bytes):
    n = len(data)
    i = 0
    while i < n:
        while i < n and data[i] <= 32:
            i += 1
        if i >= n:
            break
        x = 0
        while i < n and data[i] > 32:
            x = x * 10 + (data[i] - 48)
            i += 1
        yield x

def main():
    data = sys.stdin.buffer.read()
    it = ints_from_bytes(data)
    N = next(it)

    T = array('I', [0]) * (N + 1)
    indeg = array('I', [0]) * (N + 1)

    for i in range(1, N + 1):
        t = next(it)
        T[i] = t
        indeg[t] += 1

    q = deque()
    for i in range(1, N + 1):
        if indeg[i] == 0:
            q.append(i)

    removed = bytearray(N + 1)
    while q:
        v = q.popleft()
        if removed[v]:
            continue
        removed[v] = 1
        u = T[v]
        indeg[u] -= 1
        if indeg[u] == 0:
            q.append(u)

    visited = bytearray(N + 1)
    cycles = 0
    for i in range(1, N + 1):
        if removed[i] or visited[i]:
            continue
        cycles += 1
        cur = i
        while not visited[cur]:
            visited[cur] = 1
            cur = T[cur]

    ans = N - cycles
    sys.stdout.write(str(ans) + "\n")

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.