[LeetCode] 565. Array Nesting

題目給一組長度為n陣列nums，其元素從[0,n-1]，陣列中元素並未排列，求最長的nested陣列。

原題連結：https://leetcode.com/problems/array-nesting/

nested陣列定義為：nums[k], nums[nums[k]], ...直到元素重複為止。

思路：這題可以思考為Union-find考題，同一個nested陣列會指向同一個root。例如，nums為[5,4,0,3,1,6,2]，如下圖

從nums[0]=5出發，依序會經過nums[nums[0]]=6, nums[nums[nums[0]]]=2, nums[nums[nums[nums[0]]]]=0，然後再回到5，可以想成在遍歷nums[i]的時候，把i=0和nums[0]=5的root指向一起。然後再求所有root相同之最長子集合。

C++版本

int findroot(vector<int>& root, int i) {
    while (root[i] != i) {
        root[i] = root[root[i]]; // path compression
        i = root[i];
    }
    return i;
}
int arrayNesting(vector<int>& nums) {
    vector<int> root(nums.size());
    unordered_map<int,int> map; // count max length
    int cnt = 0;
    // assign itself as root
    for (int i=0; i<nums.size(); i++) {
        root[i] = i;
    }
    // union all elements
    for (int i=0; i<nums.size(); i++) {
        int r1 = findroot(root, i);
        int r2 = findroot(root, nums[i]);
        if (r1 != r2) {
            root[r2] = r1;
        }
    }
    // count the subset having the same root
    for (int i=0; i<root.size(); i++) {
        int r = findroot(root, root[i]);
         if (map.count(r)) {
            map[r] += 1;
        } else {
            map[r] = 1;
        }
        cnt = max(cnt, map[r]);
    }
    return cnt;
}

Time Complexity: O(n)

Space Complexity: O(n)