問題概要

$N$ 個のボタンがある。ボタン $i$ が光っているときにそのボタンを押すと、ボタン $i$ の明かりが消え、その後ボタン $a_{i}$ が光る（ $a_{i} = i$ であることもある）。

最初、ボタン 1 が光っていて、ボタン 2 が光るまでボタンを押していきたい。そのようなことは可能かどうか判定し、もし可能なら最低で何回ボタンを押す必要があるかを求めよ。

制約

$2 \le N \le 10^{5}$

考えたこと

まず、例によって 0-indexed で考えることにする。つまり、最初はボタン 0 が光っていて、ボタン 1 が光るまでボタンを押していくことにする。

基本的には、次のようなシミュレーションをすればよいと思われる。

int res = 0;   // 回数
int cur = 0;  // 今光っているボタン
while (cur != 1) {
    cur = a[cur];   // ボタンを押す (新たに光るボタンの番号を cur に代入)
    res++;
}
cout << res << endl;

しかしながら、無限回ボタンを押しても、ボタン 2 にたどり着かない場合もあるのだ。それは「ボタン 2 を含まないような無限ループに陥ってしまう場合」である。

それを検出するためには、「すでに訪れた頂点」を管理してあげて、同じ頂点を二度訪れたときに「無限ループに入ってしまった」と判定して、シミュレーションを打ち切れば良い。そして、-1 を出力すればよい。

「すでに訪れた頂点」の管理は、次のようなバケット配列を用いればよい。

seen[v]：頂点 $v$ をすでに訪れたとき True / そうでないとき False

以上の解法の計算量は $O(N)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; i++) cin >> a[i], a[i]--;

    int res = 0, cur = 0;
    vector<int> seen(N, false);  // 重複判定用
    while (cur != 1) {
        seen[cur] = true;
        cur = a[cur];  // 次の頂点へ遷移させる
        res++;  // カウンタを回す

        if (seen[cur]) {
            // すでに訪れた頂点に到達してしまったら、ループしてしまう
            // ゆえに、頂点 1 へは辿り着けない
            cout << -1 << endl;
            return 0;
        }
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 065 B - Trained? (4Q, 茶色, 200 点)

問題概要

制約

考えたこと

コード