LeetCode 565. Array nesting

565. Array nesting

【DFS】 Because there are no repeating elements , Therefore, there will be no case that one vertex connects multiple vertices , So set up a visit Array , For each vertex dfs, If this vertex has been visited , It shows that he forms a ring . On the next vertex dfs Judge whether you have visited , If you have visited , It means that it is already in the ring .

In fact, it will be better understood if it is changed here

0 -> 5

1 -> 4

2 -> 0

3 -> 3

4 -> 1

5 -> 6

6 -> 2

In fact, it is an undirected graph , Just looking for the ring

class Solution {

    // dfs

    public int arrayNesting(int[] nums) {
        int[] visit = new int[nums.length];
        int max = 0;
        for (var i = 0; i < nums.length; i++) {
            if (visit[i] == 1) continue;
            int idx = i, t = 0;
            while(true) {
                if (visit[idx] == 1) {
                    max = Math.max(max, t);
                    break;
                }
                t++;
                visit[idx] = 1;
                idx = nums[idx];
            }
        }
        return max;
    }
}

【 Union checking set 】 You can also find rings by using the union search set , Put on the same ring union get up , Then judge each union Just the size of

class Solution {

    int[] f = new int[100001];

    public int ask(int x) {
        if (x == f[x]) return x;
        return f[x] = ask(f[x]);
    }

    public void union(int x, int y) {
        f[ask(x)] = ask(y);
    }

    public int arrayNesting(int[] nums) {
        int n = nums.length;
        for (var i = 1; i <= n; i++) f[i] = i;
        for (var i = 0; i < n; i++) union(nums[i], i);
        int[] cnt = new int[n + 1];
        int ans = 0;
        for (var i = 0; i < n; i++) {
            ans = Math.max(ans, ++cnt[ask(i)]);
        }
        return ans;
    }
}