सी ++ में ऐरे नेस्टिंग

मान लीजिए कि हमारे पास शून्य-अनुक्रमित सरणी A लंबाई N है जिसमें 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]]]… उस सादृश्य से, हम एस में एक डुप्लिकेट तत्व होने से ठीक पहले जोड़ना बंद कर देते हैं। इसलिए यदि सरणी ए =[5,4,0,3,1,6,2] की तरह है, तो आउटपुट 4 होगा, जैसा कि ए [ 0] =5, ए [1] =4, ए [2] =0, ए [3] =3, ए [4] =1, ए [5] =6, और अंत में ए [6] =2.

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

इसलिए dfs नाम का एक फंक्शन बनाएं। यह नोड, एआर सरणी, वी सरणी, और एक सेट का दौरा करेगा। निम्नलिखित को dfs सरणी में करें -
यदि नोड का दौरा किया जाता है, तो वापस आएं
नोड को v में डालें, नोड को विज़िट किया गया के रूप में चिह्नित करें
dfs(arr[node], arr, v, देखे गए)
मुख्य विधि से, निम्न कार्य करें -
ret:=0, n:=अंकों का आकार। विज़िट नामक एक सेट बनाएं
मैं के लिए 0 से n - 1 की सीमा में
- एक सरणी v बनाएं
- यदि nums[i] का दौरा नहीं किया जाता है, तो dfs(nums[i], nums, v, विज़िट किया गया)
- ret :=अधिकतम रिट और v का आकार
रिटर्न रिटर्न

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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]