Overview

When each firework \(i\) is launched, it destroys target \(T_i\). This structure forms a “directed graph where each node has out-degree exactly 1 (functional graph).” The problem of maximizing the number of launched fireworks reduces to counting the number of cycles in this graph, and the answer is \(N - (\text{number of cycles})\).

Analysis

Understanding the Graph Structure

By drawing an edge from each firework \(i\) to firework \(T_i\), we obtain a directed graph where every node has out-degree exactly 1 (functional graph). This graph consists of several cycles and trees flowing into those cycles (ρ-shaped structures).

Nodes Not Belonging to Cycles (Tree Parts)

For a node \(i\) that does not belong to a cycle, if \(i\) is launched first, it destroys \(T_i\), but if \(T_i\) is launched first, \(i\) is not destroyed. Therefore, by launching in the appropriate order (from leaves toward the root of the tree), all nodes in the tree parts can be launched without being destroyed.

Loss from Cycle Parts

The problem lies in the cycles. Consider a cycle \(v_1 \to v_2 \to \cdots \to v_k \to v_1\). Launching \(v_1\) destroys \(v_2\), launching \(v_2\) destroys \(v_3\), and so on.

No matter which node in the cycle is launched first, the shockwave from the first launched firework destroys exactly one next firework. The remaining nodes can be launched in order by skipping the destroyed one, but since the destroyed node’s shockwave does not activate, no further chain of destruction occurs.

In other words, the best we can do is that exactly one node is destroyed per cycle.

Conclusion

No nodes are lost in the tree parts, and exactly one is lost per cycle, so:

\[\text{answer} = N - (\text{number of cycles})\]

Concrete Example

For \(N = 4\), \(T = [2, 1, 4, 3]\), the edges are \(1 \to 2, 2 \to 1, 3 \to 4, 4 \to 3\), giving 2 cycles (\(\{1,2\}\) and \(\{3,4\}\)), so the answer is \(4 - 2 = 2\).

Algorithm

1. Build a functional graph by drawing an edge from each node \(i\) to \(T_i\).
2. Traverse the graph using DFS (depth-first search) and count the number of cycles.
   • Follow a path from an unvisited node; if a node currently “being explored” is reached again, one cycle is detected.
   • If a node already “fully explored” is reached, it is not a new cycle.
3. Output \(N - (\text{number of cycles})\) as the answer.

Complexity

• Time complexity: \(O(N)\) (each node is visited at most a constant number of times)
• Space complexity: \(O(N)\) (for the graph, visit states, and path recording)

Implementation Notes

• Cycle detection is straightforward in a functional graph. By simply following each node to its next node and maintaining a visited array with three states — “unvisited (0),” “being explored (1),” and “fully explored (2)” — a cycle is identified when we return to a node that is currently being explored.

• Since \(N\) can be as large as \(10^6\), recursive DFS risks stack overflow. In the code, this is avoided by iteratively following paths using a while loop.

• In Python, it is important to read input efficiently using sys.stdin.buffer.read().

  Source Code

import sys
from collections import deque

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    T = [int(input_data[i+1]) - 1 for i in range(N)]
    
    # Count cycles in functional graph
    # Each node has out-degree 1
    visited = [0] * N  # 0: unvisited, 1: in progress, 2: done
    num_cycles = 0
    
    for start in range(N):
        if visited[start] != 0:
            continue
        path = []
        node = start
        while visited[node] == 0:
            visited[node] = 1
            path.append(node)
            node = T[node]
        
        if visited[node] == 1:
            # Found a cycle - count it
            # Find where the cycle starts in path
            cycle_start = node
            idx = 0
            while path[idx] != cycle_start:
                idx += 1
            num_cycles += 1
        
        for p in path:
            visited[p] = 2
    
    print(N - num_cycles)

solve()

---

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