题意ref{:target=”_blank”}
分析可以得出,如果从i跳转到nums[i]连一条边的话,则这里存在多个环。
存在环的原因是,任何一个节点的入度和出度都为1,这里可以从题意得知。
解法就是不断计算节点,计算后标记下,然后遍历一遍一定会遍历所有的环。
C++ 代码
class Solution {
public:
int arrayNesting(vector<int>& nums) {
int n = nums.size();
vector<bool> used(n, false);
int res = 0;
for(int i=0; i<n; ++i) {
int k = nums[i];
int cur = 0;
while(!used[k]) {
used[k] = true;
cur++;
int next = nums[k];
k = next;
}
res = max(res, cur);
}
return res;
}
};