457. Circular Array Loop，用图的方法做

这题可以直接simulate，也可以用图的思想找环。
首先我们可以建一个图。
图上的node上每一个index，每个index只有一条边。
这条边可能连到别的点， 也可能是连到它自己。
对于连到他自己的点，这些点不可能有环，所以可以直接略过这些点。

然后我们从每一个点出发，一直走下去， 看会不会遇到之前已经走过的点。
我们保持一个visiting的set。
同时也保持一个visited的array, 如果遇到一个点是visited,证明这个点以前访问过，
既然以前访问时没到循环，所以就不用再找了。
如果某个点在这次访问的时候已经访问过了（出现在visiting里），则肯定有个循环。

class Solution {
    public boolean circularArrayLoop(int[] nums) {
        int N = nums.length;
        int[] nexts = new int[N];
        boolean[] visited = new boolean[N];
        
        //build graph;
        for (int i = 0; i < N; i++) {
            nexts[i] = (i + (nums[i] < 0 ? N + (nums[i] % N) : nums[i])) % N;
            if(nexts[i] == i) visited[i] = true;
        }
        for (int i = 0; i < N; i++) {
            if (!visited[i]) {
                if (dfsFoundCycle(i, nums, nexts, visited, new HashSet<>())) return true;
            }
        }
        return false;
    }
    private boolean dfsFoundCycle(int index, int[] nums, int[] nexts, boolean[] visited,
                                 Set<Integer> visiting ) {
        // every level only have at most one branch.
        if (!visiting.add(index)) return true;
        if (visited[index]) return false; //visited, no loop
        visited[index] = true;
        
        // check the next step
        int next = nexts[index];
        
        //if next step has different direction,

        if (nums[index] * nums[next] < 0) return false;
        
        if (dfsFoundCycle(next, nums, nexts, visited, visiting))  return true;
        
        return false;
    }
}