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

int 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