C++で解く「配列のネスト」問題 ― DFSで最長の連鎖を求める方法

問題の概要

長さNの0始まりの配列Aがあり、そこには0からN-1までの整数がすべて1回ずつ含まれているとします。このとき、次のような集合Sの最長の長さを求めて返すのがこの問題の目的です。

S[i] = {A[i], A[A[i]], A[A[A[i]]], …}

Sの最初の要素はインデックスiにあるA[i]から始まり、次はA[A[i]]、その次はA[A[A[i]]]というように値をたどっていきます。そして、同じ要素が再び現れる直前で追加を打ち切ります。

例として、配列が A = [5,4,0,3,1,6,2] の場合を考えてみましょう。インデックス0からスタートすると、A[0]=5 → A[5]=6 → A[6]=2 → A[2]=0 → A[0]=5（重複）となるため、重複が現れるまでにたどれる要素は4個です。よって答えは4になります。

解法のアプローチ：DFSで連鎖をたどる

この問題は、各要素から次の要素へ一方向に辺が伸びるグラフとみなすと、配列全体がいくつかの「閉路（サイクル）」に分解できることがわかります。同じ閉路に属する要素は、どこからスタートしても必ず同じ長さになります。そのため、まだ訪問していない要素から深さ優先探索（DFS）で連鎖をたどり、その長さの最大値を更新していけば答えが得られます。

DFS関数の処理内容

1. 訪問済みチェック： ノードがすでにvisitedに含まれている場合は、それ以上たどらずにすぐreturnします。
2. 記録： 現在のノードを結果用の配列vに追加し、visitedに登録して訪問済みとしてマークします。
3. 再帰呼び出し： 次のノードarr[node]に対して、自分自身を再帰的に呼び出します。

メイン処理の流れ

1. 答えを格納するretを0で初期化し、nを配列numsのサイズとします。また、訪問管理用のvisitedセットを用意します。
2. iを0からn-1までループさせます。
   • 連鎖を記録するための新しい配列vを作成します。
   • nums[i]が未訪問であれば、dfs(nums[i], nums, v, visited)を呼び出します。
   • retとvのサイズの大きい方をretに代入します。
3. 最後にretを返します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    // DFSで連鎖をたどる
    void dfs(int node, vector<int>& arr, vector<int>& v, set<int>& visited){
        if(visited.count(node)) return;   // 訪問済みなら終了
        v.push_back(node);                // 現在のノードを記録
        visited.insert(node);             // 訪問済みとしてマーク
        dfs(arr[node], arr, v, visited);  // 次のノードへ再帰
    }
    int arrayNesting(vector<int>& nums) {
        int ret = 0;
        int n = nums.size();
        set<int> visited;
        for(int i = 0; i < n; i++){
            vector<int> v;
            if(!visited.count(nums[i])) dfs(nums[i], nums, v, visited);
            ret = max(ret, (int)v.size()); // 最長の連鎖を更新
        }
        return ret;
    }
};
int main(){
    vector<int> v = {5,4,0,3,1,6,2};
    Solution ob;
    cout << ob.arrayNesting(v);
    return 0;
}

入力と出力

入力

[5,4,0,3,1,6,2]

出力

4

計算量のポイント

各要素は一度しか訪問されないため、時間計算量はO(N)、visitedセットやvの管理に必要な空間計算量もO(N)となります。なお、実際には連鎖の長さを数えるだけで十分なので、vを明示的に保持せずカウンタだけで処理することも可能です。また、元のコードのmain関数は戻り値の型が省略されていましたが、標準C++に準拠させるためにint main()としています。