atcoder.jp
問題
- N人が居ます
- 人$i$は、人$A_i$のすぐ後ろに並んでます
- 列に並んでる人の番号を順番に出力してね
成約
- $ 1 \leq N \leq 3 \times 10^{5}$
思考
- 先頭か末尾が分かれば辿れるねぇ
- 先頭は、$A_i$が-1の人$i$…
* じゃあ、先頭の人$i$が分かったら、その次の人は…？
* $A_i$が$i$の人$i'$…
* indexと番号で整理し直してもいいんだけど、面倒臭いみがある…？
* 入力のA_Lそのまま使いたいよね
- そもそもA_L[i]って何？
* A_L[i] := iの直前に並んでる人の番号(1_indexed)
* A_L[i] = -1の時、iの直前に並んでる人は存在しない（直前のため）
- じゃあ最後尾の人は？
* A_Lに含まれない番号$x$の人！
* 誰の前にも居ない人＝最後尾！
* 末尾の人の、1つ前は…？
* A_L[末尾の人の番号] = 末尾の人の番号！
- 後ろからみていくとスムーズだったという話
コード
N = int(input())
A_L = list(map(int, input().split()))
s = set(range(1,N+1))
for a in A_L:
if a in s:
s.remove(a)
ans_L = []
num = s.pop()
while True:
ans_L.append(num)
num = A_L[num-1]
if num == -1:
break
print(*ans_L[::-1])
