ループ（閉路）を一括処理する問題はqueueを使おう委員会

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

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

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

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

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

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

　具体的に言うと、

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

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

# 具体的な問題とコード

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

```c++
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;
}
```

[提出](https://atcoder.jp/contests/abc167/submissions/44250188)

# 図解

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/fc6a70c0-6eb1-b780-6c52-b09cff7bc02b.png)


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

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

![プレゼンテーション1.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/6aa02793-cfe8-7cd2-597b-8624c518ccd3.gif)

　この結果、

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

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

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

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

![プレゼンテーション2.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/789d8e8b-75b0-336d-012d-3b40735e4c22.gif)


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

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

![プレゼンテーション3.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/fad0d56c-e4be-6ebb-8e6d-58df6d728561.gif)

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

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/443e3993-96c1-f937-64d6-83d1b4761836.png)

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

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

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

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

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

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