C ++中的数组嵌套
假设我们有一个长度为N的零索引数组A，其中包含从0到N-1的所有整数。我们必须找到并返回集合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]，那么输出将为4，即A[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，已访问）
从主要方法中，执行以下操作-
ret：=0，n：=nums的大小。制作一组称为Visited
对于i，范围为0至n–1
创建一个数组v
如果未访问nums[i]，则dfs（nums[i]，nums，v，已访问）
ret：=ret的最大值和v的大小
返回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