สมมติว่าเรามีอาร์เรย์ A แบบไม่มีดัชนีที่มีความยาว N ที่มีจำนวนเต็มทั้งหมดตั้งแต่ 0 ถึง 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] ผลลัพธ์จะเป็น 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 ทำชุดที่เรียกว่าเยี่ยมชม
- สำหรับ i ในช่วง 0 ถึง n – 1
- สร้างอาร์เรย์ v
- ถ้าไม่ได้เยี่ยมชม nums[i] แสดงว่า dfs(nums[i], nums, v, เข้าชมแล้ว)
- 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
