A zero-indexed array A of length N contains all integers from 0 to N-1. Find and return the longest length of set S, where S[i] = {A[i], A[A[i]], A[A[A[i]]], ... } subjected to the rule below.

Suppose the first element in S starts with the selection of element A[i] of index = i, the next element in S should be A[A[i]], and then A[A[A[i]]]… By that analogy, we stop adding right before a duplicate element occurs in S.

Example 1:

Input: A = [5,4,0,3,1,6,2]
Output: 4
Explanation: 
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.

One of the longest S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}


Note:

N is an integer within the range [1, 20,000].
The elements of A are all distinct.
Each element of A is an integer within the range [0, N-1].

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Data structures

Graph traversal

Starter code: class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        

Solutions:
class Solution:

	def arrayNesting(self, nums):
		best = 0
		n = len(nums)
		p = []
		for i in range(len(nums)):
			j = i
			current = 0
			while nums[j] != -1:
				current += 1
				n -= 1
				k = j
				j = nums[j]
				nums[k] = -1
			best = max(best, current)
			if n <= best:
				return best
		return best


class Solution:

	def arrayNesting(self, nums):
		maxlen = 0
		for i in range(0, len(nums)):
			cur = nums[i]
			if cur >= 0:
				curlen = 0
				nums[i] = -1
				while cur >= 0:
					j = cur
					cur = nums[j]
					nums[j] = -1
					curlen = curlen + 1
				if curlen > maxlen:
					maxlen = curlen
		return maxlen


class Solution:

	def arrayNesting(self, nums):
		dic = set()
		ma = 0
		for i in nums:
			if i not in dic:
				set_ = set()
				while i not in set_:
					set_.add(i)
					i = nums[i]
				ma = max(ma, len(set_))
				dic.update(set_)
		return ma


class Solution:

	def arrayNesting(self, nums):
		(ans, step, n) = (0, 0, len(nums))
		signal = [False] * n
		for i in range(n):
			while not signal[i]:
				signal[i] = True
				step += 1
				i = nums[i]
				ans = max(ans, step)
			step = 0
		return ans


class Solution:

	def arrayNesting(self, nums):
		longest = 1
		for i in range(len(nums)):
			count = 1
			if i == nums[i]:
				continue
			index = nums[i]
			nums[i] *= -1
			flag = True
			while flag:
				if index < 0:
					flag = False
					continue
				if nums[index] == 0:
					count += 1
					tmp = index
					index = nums[index]
					nums[tmp] = -20001
				if nums[index] > 0:
					count += 1
					tmp = index
					index = nums[index]
					nums[tmp] *= -1
				else:
					if count > longest:
						longest = count
					flag = False
		return longest


class Solution:

	def arrayNesting(self, nums):
		maxLength = 0
		for i in range(len(nums)):
			length = 0
			j = i
			while nums[j] >= 0:
				length += 1
				tmp = nums[j]
				nums[j] = -1
				j = tmp
			maxLength = max(maxLength, length)
		return maxLength


class Solution:

	def arrayNesting(self, nums):
		curr = 0
		maxLen = 0
		tovisit = set([i for i in range(len(nums))])
		while len(tovisit) > 0:
			p = tovisit.pop()
			curr = 1
			while nums[p] != -1 and nums[p] in tovisit:
				tovisit.remove(nums[p])
				(nums[p], p) = (-1, nums[p])
				curr += 1
			maxLen = max(maxLen, curr)
		return maxLen