Lồng mảng (Array Nesting) trong C++

Cho mảng A độ dài N chứa hoán vị 0..N-1. Tìm độ dài lớn nhất của tập hợp S[i] = {A[i], A[A[i]], A[A[A[i]]], ...} dừng trước khi trùng lặp.

Ví dụ: A=[5,4,0,3,1,6,2] → độ dài lớn nhất = 4 (chu trình bắt đầu từ chỉ số 0).

Thuật toán (DFS + Mảng đánh dấu)

1. Duyệt từng chỉ số i, nếu chưa thăm → DFS theo chuỗi i → A[i] → A[A[i]]....
2. Đếm độ dài chu trình, cập nhật max.
3. Đánh dấu các node đã thăm để không xử lý lại.

Mã nguồn 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, 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;
}

Đầu vào / Đầu ra

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

Output: 4