D - Firework Elimination Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は花火大会の演出を担当しています。夜空には N 発の花火が打ち上げ準備されており、それぞれ 1 から N までの番号が付いています。

各花火には、打ち上げ準備中・打ち上げ済み・消滅 の 3 つの状態があります。最初、すべての花火は打ち上げ準備中の状態です。

各花火 i（1 \leq i \leq N）には「衝撃波の対象」となる花火番号 T_i が設定されています（T_i \neq i）。

青木君は演出家として、花火を一発ずつ選んで打ち上げる順番を決めます。具体的には、以下の手順で花火大会が進みます。

  1. 青木君は打ち上げ準備中の花火の中から 1 発を選び、打ち上げる。打ち上げた花火の状態は打ち上げ済みとなり、演出リストの末尾に記録される。
  2. 打ち上げた花火を i とする。花火 i の衝撃波の対象である花火 T_i がまだ打ち上げ準備中であれば、花火 T_i は暴発し、状態が消滅に変わる（演出リストには記録されない）。花火 T_i がすでに打ち上げ済みまたは消滅であれば、何も起こらない。
  3. 打ち上げ準備中の花火が 1 発以上残っていれば手順 1 に戻る。打ち上げ準備中の花火がなくなったら花火大会は終了する。

注意： 消滅した花火は打ち上げることができません。また、消滅した花火が衝撃波を発することはなく、消滅によって連鎖的に他の花火が暴発することはありません。

花火大会が終了すると、演出リストが確定します。青木君は、演出リストに記録される花火の数（すなわち、打ち上げ済みとなった花火の数）をできるだけ多くしたいと考えています。

青木君が最適に花火を選んだとき、演出リストに記録される花火の数の最大値を求めてください。

制約

  • 2 \leq N \leq 10^6
  • 1 \leq T_i \leq N（1 \leq i \leq N）
  • T_i \neq i（1 \leq i \leq N）
  • 入力はすべて整数である。

入力

N
T_1 T_2 \cdots T_N
  • 1 行目には、花火の数 N が与えられる。
  • 2 行目には、各花火 i（1 \leq i \leq N）の衝撃波の対象を表す花火番号 T_i が、スペース区切りで N 個与えられる。

出力

青木君が最適に行動したときの、演出リストに記録される花火の数の最大値を 1 行で出力せよ。

入力例 1

4
2 1 4 3

出力例 1

2

入力例 2

4
2 3 4 1

出力例 2

3

入力例 3

10
2 3 1 5 6 4 1 3 6 7

出力例 3

8

入力例 4

20
2 3 1 5 6 7 8 4 10 11 12 9 14 15 13 1 2 3 9 13

出力例 4

16

入力例 5

2
2 1

出力例 5

1

Score : 400 pts

Problem Statement

Takahashi is in charge of directing a fireworks show. In the night sky, N fireworks are prepared for launch, numbered from 1 to N.

Each firework has one of three states: ready, launched, or destroyed. Initially, all fireworks are in the ready state.

For each firework i (1 \leq i \leq N), a "shockwave target" firework number T_i is assigned (T_i \neq i).

Aoki, as the director, decides the order in which to launch the fireworks one by one. Specifically, the fireworks show proceeds as follows:

  1. Aoki selects one firework from among the ready fireworks and launches it. The launched firework's state becomes launched, and it is recorded at the end of the performance list.
  2. Let i be the launched firework. If firework T_i, the shockwave target of firework i, is still in the ready state, then firework T_i detonates prematurely and its state changes to destroyed (it is not recorded in the performance list). If firework T_i is already launched or destroyed, nothing happens.
  3. If one or more ready fireworks remain, return to step 1. If no ready fireworks remain, the fireworks show ends.

Note: Destroyed fireworks cannot be launched. Additionally, destroyed fireworks do not emit shockwaves, and destruction does not cause chain detonations of other fireworks.

When the fireworks show ends, the performance list is finalized. Aoki wants to maximize the number of fireworks recorded in the performance list (that is, the number of fireworks that were launched).

Determine the maximum number of fireworks recorded in the performance list when Aoki chooses optimally.

Constraints

  • 2 \leq N \leq 10^6
  • 1 \leq T_i \leq N (1 \leq i \leq N)
  • T_i \neq i (1 \leq i \leq N)
  • All input values are integers.

Input

N
T_1 T_2 \cdots T_N
  • The first line gives the number of fireworks N.
  • The second line gives N space-separated integers, where T_i represents the shockwave target firework number for each firework i (1 \leq i \leq N).

Output

Output in one line the maximum number of fireworks recorded in the performance list when Aoki acts optimally.

Sample Input 1

4
2 1 4 3

Sample Output 1

2

Sample Input 2

4
2 3 4 1

Sample Output 2

3

Sample Input 3

10
2 3 1 5 6 4 1 3 6 7

Sample Output 3

8

Sample Input 4

20
2 3 1 5 6 7 8 4 10 11 12 9 14 15 13 1 2 3 9 13

Sample Output 4

16

Sample Input 5

2
2 1

Sample Output 5

1