ধরুন আমাদের দৈর্ঘ্যের 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]]]... সেই সাদৃশ্য অনুসারে, 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 নামে একটি ফাংশন তৈরি করুন। এটি নোড, অ্যারের অ্যারে, ভি অ্যারে এবং একটি সেট পরিদর্শন করবে। dfs অ্যারে - -এ নিম্নলিখিতগুলি করুন৷
- যদি নোড পরিদর্শন করা হয়, তাহলে ফিরে আসুন
- v-এ নোড ঢোকান, নোডকে ভিজিট করা হিসেবে চিহ্নিত করুন
- dfs(arr[node], arr, v, visited)
- প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
- ret :=0, n :=সংখ্যার আকার। ভিজিটড নামে একটি সেট তৈরি করুন
- আমি 0 থেকে n – 1
- পরিসরে
- একটি অ্যারে তৈরি করুন v
- যদি nums[i] পরিদর্শন না করা হয়, তাহলে dfs(nums[i], nums, v, visited)
- ret :=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]
আউটপুট
4
