C++での配列の入れ子

0からN-1までのすべての整数を含む長さNのゼロインデックス配列Aがあるとします。セットSの最長の長さを見つけて返す必要があります。ここで、S [i] ={A [i]、A [A [i]]、A [A [A [i]]]、...}以下のルール。ここで、Sの最初の要素がインデックス=iの要素A[i]の選択で始まり、Sの次の要素はA [A [i]]であり、次にA [A[A[i]]]…であると考えます。そのアナロジーにより、Sで重複要素が発生する直前に追加を停止します。したがって、配列がA =[5,4,0,3,1,6,2]の場合、出力はA[として4になります。 0] =5、A [1] =4、A [2] =0、A [3] =3、A [4] =1、A [5] =6、最後にA [6]=2。

これを解決するには、次の手順に従います-

• したがって、dfsという関数を作成します。これにより、ノード、arr配列、v配列、および訪問されたセットが取得されます。 dfs配列で次の手順を実行します-
• ノードにアクセスした場合は、戻ります
• ノードをvに挿入し、ノードを訪問済みとしてマークします
• dfs（arr [node]、arr、v、visited）
• メインの方法から、次の手順を実行します-
• ret：=0、n：=numsのサイズ。訪問済みと呼ばれるセットを作成する
• 0からn–1の範囲のiの場合
  • アレイを作成するv
  • nums [i]にアクセスしていない場合は、dfs（nums [i]、nums、v、visited）
  • ret：=retの最大値とvのサイズ
• return ret

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   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;
   }
};
main(){
   vector<int> v = {5,4,0,3,1,6,2};
   Solution ob;
   cout << (ob.arrayNesting(v));
}

入力

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

出力

4