前提：記事中におけるグラフは、次の頂点 = f(現在の頂点) の形でグラフが定義される、いわゆる functional graph と呼ばれるものを想定しています。

　大量のシミュレーションが必要で、愚直に実装すると TLE するけど、実はある部分はループ（閉路）を繰り返すだけで本当にシミュレーションが必要な部分は少ないという問題は時々出ます。同じことを少し前に書きました。その時は「SCC（強連結成分分解）を使うとクールだぜ！」という思いでいたのですが、その後、ダブリング（参考リンク）を覚えると「やはりダブリングが最強では……？」となりました。しかし、私はこの度、新たな結論にたどり着きました。

　queue を使う解法こそが最強である、と。

　なんだか、しゃくとり法でも同じことを言った気がします。ちなみに、記事を書いた甲斐もあって賛同者も増えているようです（ありがとうございます）。これに続き、この度、私は新しい委員会「ループ（閉路）を一括処理する問題は queue を使おう委員」を発足しようと思います。

なぜループの処理は面倒なのか？

　なぜループの処理が面倒なのかというと、「ループにいつ入ったかの検出」「ループサイズの検出」「ループの手前で止まっているかの判定」が必要だからです。これらをすべてカーソル位置基準で考えると、慣れていないと頭がバグります。以前提案した、SCC を使った手法では、これらをステップバイステップで処理できるため、コードの見通しやデバッグのしやすさが向上します。今回提案する queue を使う手法では、外部ライブラリのインクルードも必要なく、よりコードが簡潔になります。

　具体的に言うと、

ループにいつ入ったかの検出を、カーソル位置を気にせず行うことができる
ループサイズの検出を、カーソル位置を気にせず行うことができる
ループの手前で止まる場合も自然にシミュレーションできる

　というメリットがあります。

具体的な問題とコード

int main()
{
    int n;
    ll k;
    cin >> n >> k;
    vector<int> a(n);
    cin >> a;
    rep(i, n)
    {
        a[i]--;
    }
    queue<int> q;
    int now = 0;
    vector<bool> seen(n);
    while (!seen[now])
    {
        q.push(now);
        seen[now] = true;
        now = a[now];
    }
    while (q.front() != now && k)
    {
        q.pop();
        k--;
    }
    k %= q.size();
    while (k--)
    {
        q.pop();
    }
    cout << q.front() + 1 << endl;
}

提出

図解

　具体的な図で考えてみましょう。

　このような有向グラフを考えます。

　「0」のノードから始まり、一度訪れた点に再び訪れるまでキューを埋めます。

　この結果、

now = 5
q = {0,2,5,11,7,1,6,12,4,8}

　という、ふたつの情報が得られます。

ループにそもそも入らない場合

　移動回数が少なくてそもそもループに入らない場合、例えば 1 回だけ移動する場合を考えます。この場合は、普通に移動回数分だけ queue を pop すれば、残された queue の先頭が答えになります。これはほぼ自明かと思います。

　この例では「2」のノードが答えになります。

ループに入る場合

　
　次に、移動回数が多くてループに入る場合を考えます。まず、ループに入る直前までをシミュレーションします。now（＝ループの開始地点）が「5」という情報があるので、これが queue の先頭に来るまで、回数を減らしながら pop を繰り返します。

　この時、重要な事実として、queue の配列はループの要素だけを含みます。つまり、以下のことが言えます。

ループに入るまでの導入となる移動回数を使い切ったこと
queue の長さがそのままループの長さとなること

　これらの情報を、カーソルの位置や場合分けを一切気にせずに知ることができます。

　あとは、単純に操作回数をループ長で割ったあまりをシミュレーションすれば良いだけです。

これらをコードでまとめると

　以上のステップは、コードではこれだけの部分で表現することができます。

    while (q.front() != now && k)
    {
        q.pop();
        k--;
    }
    k %= q.size();
    while (k--)
    {
        q.pop();
    }

　ループに入る場合もそうでない場合も、この操作の後の q.front() が答えになります。シンプル～～。