AtCoder Beginner Contest 167 D - Teleporter【Python】

https://atcoder.jp/contests/abc167/tasks/abc167_d

AtCoder ProblemsでDifficulty: 754、Solve Probability: 35%でした。

最終的に経路はリピートされるため、辞書で町ごとに訪れた回数をカウントし、初めてカウントが2になった街があれば、その時点からその街のカウントが3になるまでの経路をリストで管理しループから抜けるようにしました。

from collections import defaultdict

N, K = map(int, input().split())
A = list(map(int, input().split()))

d = defaultdict(int)
c = 0
d[c] += 1
rep_flag = False
rep = []
n_before_rep = 1
for i in range(K):
    c = A[c] - 1
    d[c] += 1
    if d[c] == 3:
        print(rep[(K + 1 - n_before_rep) % len(rep) - 1] + 1)
        exit()
    if d[c] == 2:
        rep_flag = True
    if rep_flag:
        rep.append(c)
    else:
        n_before_rep += 1
print(c + 1)