565.数组嵌套

链接：565.数组嵌套
难度：Medium
标签：深度优先搜索、数组
简介：索引从 0 开始长度为 N 的数组 A，包含 0 到 N - 1 的所有整数。找到最大的集合 S 并返回其大小。

题解 1 - cpp

• 编辑时间：2022-07-17
• 执行用时：364ms
• 内存消耗：167.9MB
• 编程语言：cpp
• 解法介绍：遍历，记录环大小。

class Solution {
   public:
    int arrayNesting(vector<int> &nums) {
        int ans = 0, n = nums.size();
        vector<int> m(n, -1);
        for (int i = 0; i < n; i++) {
            if (m[i] != -1) continue;
            unordered_set<int> s;
            int res = dfs(nums, m, s, i);
            ans = max(ans, res);
            for (auto &idx : s) m[idx] = res;
        }
        return ans;
    }
    int dfs(vector<int> &nums, vector<int> &m, unordered_set<int> &s, int idx) {
        if (m[idx] != -1) return m[idx];
        if (s.count(idx)) return 0;
        s.insert(idx);
        return dfs(nums, m, s, nums[idx]) + 1;
    }
};