ধরুন আমাদের একটি শূন্য-ইন্ডেক্সড অ্যারে A আছে যার দৈর্ঘ্য N এবং এতে ০ থেকে N-1 পর্যন্ত সব পূর্ণসংখ্যা রয়েছে। আমাদের সেট S-এর সর্বোচ্চ দৈর্ঘ্য খুঁজে বের করতে হবে এবং ফেরত দিতে হবে, যেখানে S[i] = {A[i], A[A[i]], A[A[A[i]]], ... } নিচের নিয়মাবলী অনুযায়ী। এখন S-এর প্রথম উপাদান A[i] ইনডেক্স i নির্বাচন দিয়ে শুরু হয়, S-এর পরবর্তী উপাদান হবে A[A[i]], তারপর A[A[A[i]]]... এই সাদৃশ্য অনুযায়ী, আমরা S-এ ডুপ্লিকেট উপাদান হওয়ার ঠিক আগে যোগ করা বন্ধ করি। তাই যদি অ্যারে হয় A = [5,4,0,3,1,6,2], তবে আউটপুট হবে ৪, কারণ 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 অ্যারেতে নিম্নলিখিত কাজ করুন −
- যদি node visited হয়, তবে ফেরত যান
- node v-এ যোগ করুন, node কে visited হিসেবে চিহ্নিত করুন
- dfs(arr[node], arr, v, visited)
- মূল মেথড থেকে, নিম্নলিখিত কাজ করুন −
- ret := ০, n := nums-এর আকার। একটি visited সেট তৈরি করুন
- i = 0 থেকে n – ১ পর্যন্ত
- একটি v অ্যারে তৈরি করুন
- যদি nums[i] visited না হয়, তবে dfs(nums[i], nums, v, visited)
- ret := ret এবং v-এর আকারের মধ্যে max
- 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
