Untitled

 avatar
unknown
plain_text
2 years ago
1.2 kB
3
Indexable
class Solution {
    int ret;
    public int longestCycle(int[] A) {
        int n = A.length;
        ret = -1;
        Map<Integer, Integer> step = new HashMap<>();
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (A[i] == -1) {
                visited[i] = true;
            }
            if (!visited[i]) {
                visited[i] = true;
                step.clear();
                helper(A, i, step, visited, 1);
            }
        }
        return ret;
    }

    void helper(int[] A, int cur, Map<Integer, Integer> step, boolean[] visited, int curStep) {
        int n = A.length;
        step.put(cur, curStep);
        // step[cur] = curStep;
        int next = A[cur];
        if (next == -1) {
            return;
        }
        if (visited[next]) {
            if (step.containsKey(next)) {
                int len = curStep - step.get(next).intValue() + 1;
                ret = Math.max(ret, len);
            }
        } else {
            visited[next] = true;
            if (A[next] == -1) {
                return;
            }
            helper(A, next, step, visited, curStep + 1);
        }
    }
}
Editor is loading...