C++プログラムで3つの要素が互いに「好き」かどうか（3項間の循環関係）をチェックする方法

n個の要素からなる配列Aを考えます。地球上にはn台の飛行機があり、それぞれ1からnまでの番号が付けられています。番号iの飛行機は、番号A[i]の飛行機を「好き」であることが保証されており、A[i] ≠ i（自分自身を好きになることはない）が常に成り立ちます。

このとき、「飛行機pはqを好き、qはrを好き、そしてrはpを好き」という3台の飛行機による循環関係が存在するかどうかを判定するのがこの問題です。

例えば、入力が A = [2, 4, 5, 1, 3] の場合、出力は True になります。これは、飛行機2は4を好き（A[2]=4）、飛行機4は1を好き（A[4]=1）、飛行機1は2を好き（A[1]=2）というように、{1, 2, 4} の3台が互いに好きで循環しているためです。

解法の考え方

この問題は、各飛行機について「好き」の関係を3段階たどった先が自分自身に戻ってくるかを確認するだけで解決できます。飛行機iが好きな相手はA[i]、その相手が好きなのはA[A[i]]、さらにその先はA[A[A[i]]]です。もしA[A[A[i]]] == i が成り立てば、長さ3の循環が存在することが分かります。

手順

以下のステップで解いていきます。

n := Aのサイズ
i := 0 で初期化し、i < n の間、i を 1 ずつ増やしながら繰り返す:
    もし A[A[A[i + 1]]] が i + 1 と等しい場合:
        true を返す
false を返す

C++での実装例

それでは、実際の実装を見て理解を深めましょう。ここでは、1始まりの飛行機番号と0始まりの配列添字のずれに注意し、範囲外アクセスを避けた安全なコードにしています。

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

bool solve(vector<int> A) {
    int n = A.size();
    // 各飛行機について「好き」の関係を3段階たどる
    for (int i = 0; i < n; i++) {
        int second = A[i] - 1;        // i番目の飛行機が好きな相手
        int third = A[second] - 1;    // さらにその相手が好きな飛行機
        if (A[third] - 1 == i) {      // 3段階先が元の飛行機に戻れば循環成立
            return true;
        }
    }
    return false;
}

int main() {
    vector<int> A = { 2, 4, 5, 1, 3 };
    cout << solve(A) << endl;   // 1（true）が出力される
    return 0;
}

入力

{ 2, 4, 5, 1, 3 }

出力

1

計算量

時間計算量はO(n)、空間計算量はO(1)です。各飛行機について定数回の配列参照を行うだけなので、非常に効率的に判定できます。