Java DFS code with explanation in comments, Easy to understand


  • 0
    public class Solution {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            
            List<List<Integer>> gList = new ArrayList<List<Integer>>();
            
            //Create a graph from the input
            for(int i = 0; i < numCourses; ++i) {
                gList.add(new ArrayList());
            }
            for(int i = 0; i < prerequisites.length; ++i) {
                gList.get(prerequisites[i][1]).add(prerequisites[i][0]);
            }
            
            boolean visited[] = new boolean[numCourses]; // visited array to keep a track of unique nodes
            Set<Integer> check = new HashSet(); // set for checking cycles
            
            int[] retArray = new int[numCourses];
            
            Stack<Integer> orderStack = new Stack(); // stack for making the topological ordering
            
            for(int i = 0; i < gList.size(); ++i) {
                if(!visited[i]) {
                    // if the graph contains a cycle then return an empty array
                    if(hasCycle(gList, check, orderStack, visited, i)) {
                        return new int[]{};
                    }
                }
            }
            
            int i = 0;
            while(!orderStack.isEmpty()) {
                retArray[i] = orderStack.pop(); //pop the stack to ensure the correct topological ordering
                i++;
            }
            return retArray;
        }
        
        private boolean hasCycle(List<List<Integer>> gList, Set<Integer> check, Stack<Integer> orderStack, boolean[] visited, int course) {
            if(!visited[course]) {
                visited[course] = true;
                check.add(course);
                for(int i = 0; i < gList.get(course).size(); ++i) {
                    // dfs call
                    if(!visited[gList.get(course).get(i)] && hasCycle(gList, check, orderStack, visited, gList.get(course).get(i))) return true; 
                    else if(check.contains(gList.get(course).get(i))) return true; //check whether the node in the graph is being visited again so that there is a cycle
                }
            }
            check.remove(course); // remove the node 
            orderStack.push(course); // push the node after all its adjacent dependent nodes are pushed onto the stack
            return false;
        }
    }
    

Log in to reply
 

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