5ms Elegant Java DFS + BFS Toposort, Beats 98%!


  • 0
    V

    DFS

        public boolean canFinish(int numCourses, int[][] prerequisites) {
            List<Integer>[] matrix = new List[numCourses];
            int[] visited = new int[numCourses];
            
            // initialize adjacency list and indegree list
            for(int i=0; i<prerequisites.length; i++) {
                int[] edge = prerequisites[i];
                if (matrix[edge[1]] == null) {
                    matrix[edge[1]] = new ArrayList();
                }
                matrix[edge[1]].add(edge[0]);
            }
            
            for(int i=0; i<numCourses; i++) {
                if (visited[i] == 0) { // only visit unvisited nodes
                    if(!dfs(matrix, visited, i)) return false;
                }
            }
            
            return true;
        }
        
        public boolean dfs(List<Integer>[] matrix, int[] visited, int i) {
            if (visited[i] == 1) return false; // cycle detected
            if (visited[i] == 2) return true; // if fully visited, there is no chance for cycle
            if (matrix[i] == null) { // no outgoing edges, so we can say it is fully visited
                visited[i] = 2;
                return true;
            }
    
            visited[i] = 1; // temp mark, signifys visited on same path, used for cycle detection
            for(Integer adj : matrix[i]) { // dfs step
                if (!dfs(matrix, visited, adj)) return false;
            }
            
            visited[i] = 2; // permanent mark, fully visited all children
            return true;
        }
    

    For fun, here is 9ms BFS solution

        public boolean canFinish(int numCourses, int[][] prerequisites) {
            List<Integer>[] matrix = new List[numCourses];
            int[] indegree = new int[numCourses];
            Queue<Integer> q = new LinkedList();
            int count = 0;
    
            //build graph representation as adjacency list
            for(int i=0; i<prerequisites.length; i++) {
                int[] edge = prerequisites[i];
                if (matrix[edge[1]] == null) {
                    matrix[edge[1]] = new ArrayList();
                }
    
                matrix[edge[1]].add(edge[0]);
                indegree[edge[0]]++;
            }
            
            // add all nodes that have 0 pre-reqs as start points
            for(int i=0; i<numCourses; i++) {
                if (indegree[i] == 0) {
                    q.add(i);
                }
            }
            
            while(!q.isEmpty()) {
                int cur = q.poll();
                count++; // if we have entered the while loop, we know cur has had its pre-reqs already visited, so safe to increment count (or even add to topological ordering) here
                if (matrix[cur] == null) continue; // no out edges
                for(Integer adj : matrix[cur]) {
                    if (--indegree[adj] == 0) { // only add to queue when indegree reaches 0, that way we know all prereqs have been fulfilled
                        q.add(adj);
                    }  
                }
            }
            
            return count == numCourses;
        }
    

    Both are O(V+E) time and space


Log in to reply
 

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