At coder 167のD問題がTLEになってしまう

Question

At coder 167のD問題がTLEになってしまう理由が分かりません。自分の中では解説で見た通りのことを思いつき、実装したのですがTLEになってしまいます。どなたかAt Coderの同じ大会に参加された方などいらっしゃいましたらアドバイスいただけると嬉しいです。問題の内容は以下のURLです。
https://atcoder.jp/contests/abc167/tasks/abc167_d

n,k = map(int,input().split())
town = 1
number = [1]
l = list(map(int, input().split()))
for i in range(k):
    town -= 1
    town = l[town]
    if town == l[town-1]:
        break
    elif town in number:
        hit = number.index(town)
        waru = i - hit + 1
        naka = (k - hit) % waru
        town = number[hit + naka]
        break
    number.append(town)
print(town)

Answer 1

問題は詳しく把握していませんが、コードをぱっと見てわかることを言うと

n,k = map(int,input().split())
town = 1
number = [1]
l = list(map(int, input().split()))
for i in range(k):
    town -= 1
    town = l[town]
    if town == l[town-1]:
        break
    elif town in number:         # これは線形探索
        hit = number.index(town) # これもそうだけどbreakするとき一回呼ぶだけだから、いいか……
        waru = i - hit + 1
        naka = (k - hit) % waru
        town = number[hit + naka]
        break
    number.append(town)
print(town)

なのでO(k^2)になり、ちょっと辛いのではないかと思います。

Comments

[bluer]

解答頂きありがとうございます。
線形探索など調べていてよく耳にするのですがアルゴリズム自体を学んでおらず、勉強したいと思っています。
蟻本をやってみようと思ったのですが、C言語が分からないです。もしhayatakaさんおすすめのPythonについての本などありましたら教えてください。