[LeetCode] 565. Array Nesting

 Problem: https://leetcode.com/problems/array-nesting/

According to the given rule,  a valid set is built upon with the values of nums[k], nums[nums[k]], ...

We can use Union-Find to build set. Then return size of the largest set as result.

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
       
    def union(self, a, b):
        ap = self.find(a)
        bp = self.find(b)
        
        if ap != bp:
            self.parent[bp] = ap
     
    def find(self, a):
        if self.parent[a] != a:
            self.parent[a] = self.find(self.parent[a])
        return self.parent[a]

class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        uf = UnionFind(len(nums))
        
        # build the sets
        for a, b in enumerate(nums):
            if a != b:
                uf.union(a, b)
        
        # get size of the largest set
        count = defaultdict(int)
        
        for i in range(len(nums)):
            count[uf.find(i)] += 1
        
        return max(count.values())