Array Nesting หาความยาวชุดสูงสุดใน C++

ให้อาร์เรย์ A ขนาด N มีค่า 0 ถึง N-1 ครบหมด ต้องการหาความยาวสูงสุดของชุด S โดย S[i] = {A[i], A[A[i]], A[A[A[i]]], ...} หยุดก่อนที่จะมีค่าซ้ำ

ตัวอย่าง: A = [5,4,0,3,1,6,2] → output = 4

วิธีแก้ปัญหา (DFS + Cycle Detection)

1. สร้างฟังก์ชัน dfs(node, arr, v, visited):
   • ถ้า node ถูกเยี่ยมแล้ว → return
   • ใส่ node ลง v, ทำเครื่องหมาย visited
   • dfs(arr[node], arr, v, visited)
2. จาก main:
   • ret = 0, visited = เซตว่าง
   • วน i = 0 ถึง n-1:
     • v = อาร์เรย์ว่าง
     • ถ้า nums[i] ยังไม่ visited → dfs(nums[i], nums, v, visited)
     • ret = max(ret, ขนาด v)
   • คืนค่า ret

ตัวอย่างโค้ด C++

#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);
    return 0;
}

Input

[5,4,0,3,1,6,2]

Output

4