Java directed cycle detection solution in 8ms. Beat 84.40% Java solution


  • 0
    Z

    The idea is trivial depth first search, a simpler variance of 'Directed cycle detection' solution originated from Algorithms 4th edition.
    https://github.com/zeqli/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/DirectedCycle.java

    1. Construct an adjacent list
    2. Keep track of visited vertice (boolean[] marked) and current visiting path (boolean[] onStack)
    3. If there is a vertex that has been on stack appears in another vertex's adjacent list, then we find a cycle.
    public class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            boolean[] marked = new boolean[numCourses];
            boolean[] onStack = new boolean[numCourses];
            List<List<Integer>> adj = new ArrayList<>(numCourses);
            for (int i = 0; i < numCourses; i++){
                adj.add(new ArrayList<>());
            }
            
            for (int[] pair: prerequisites){
                List<Integer> list = adj.get(pair[0]);
                list.add(pair[1]);
            }
            
            for (int i = 0; i < numCourses; i++){
                boolean canFinish = true;
                if (!marked[i])
                    canFinish = dfs(adj, i, marked, onStack);
                if (!canFinish)
                    return false;
            }
            return true;
        }
        
        
        public boolean dfs(List<List<Integer>> adj, int v, boolean[] marked, boolean[] onStack){
            onStack[v] = true;
            marked[v] = true;
            for (int w : adj.get(v)){
                boolean canFinish = true;
                if (!marked[w]){
                    canFinish = dfs(adj, w, marked, onStack);
                } else if (onStack[w]){
                    canFinish = false;
                }
                if (!canFinish)
                    return false;
            }
            onStack[v] = false;
            return true;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.