Standard BFS method for Course Schedule II


  • 9
    F

    The idea is to start from courses upon which no other courses will depend(These courses all have the least priority and should come at the last in the order list). Then do standard BFS on these courses and try to find courses that have next level of priority(These courses will come right before the least priority courses in the order list). And continue the process until we have no more courses to deal with. If there is no cycle in the prerequisites graph, then in this way we should be able to deal with all the courses. Otherwise there will be remaining courses left untended. See the comments in the code for more information.

    public int[] findOrder(int numCourses, int[][] prerequisites) {
    	// for each course in the map nextVertex, the corresponding set contains prerequisite courses for this course 
        Map<Integer, Set<Integer>> nextVertex = new HashMap<>();
        // preVertex[i] indicates the number of courses that depend on course i
        int[] preVertex = new int[numCourses];
        
        // set up nextVertex and preVertex
        for (int i = 0; i < prerequisites.length; i++) {
        	if (!nextVertex.containsKey(prerequisites[i][0])) {
        		nextVertex.put(prerequisites[i][0], new HashSet<>());
        	}
        	
        	if (nextVertex.get(prerequisites[i][0]).add(prerequisites[i][1])) {
        		preVertex[prerequisites[i][1]]++;
        	}
        }
        
        // queue for BFS, which will only hold courses currently upon which no other courses depend
        Deque<Integer> queue = new ArrayDeque<>();
        
        for (int i = 0; i < preVertex.length; i++) {
        	// start from courses upon which no other courses depend. These courses should come last in the order list
        	if (preVertex[i] == 0) {
        		queue.offerLast(i);
        	}
        }
        
        // array for the result, which will be filled up from the end by index
        int[] res = new int[numCourses];
        int index = res.length - 1;
        
        while (!queue.isEmpty()) {
        	int key = queue.pollFirst(); // this is a course that no other courses will depend upon
        	res[index--] = key;          // so we put it at the end of the order list
        	
        	// since we are done with course "key", for any other course that course "key" is dependent on, we can decrease
        	// the corrresponding preVertex by one and check if it is qualified to be added to the queue.
        	if (nextVertex.containsKey(key)) {
        		for (int i : nextVertex.get(key)) {
        			if (--preVertex[i] == 0) {
        				queue.offerLast(i);
        			}
        		}
        	}
        	
        	--numCourses; // we are done with course "key", so reduce the remaining number of courses by 1
        }
        
        // if the remaining number of courses is not zero, then we cannot complete all the courses; otherwise return the result
        return numCourses == 0 ? res : new int[0];
    }

  • 0
    I

    what if there are multiple sinks and the path start from the first fails.


  • 0
    F

    If we cannot find a starting point, then there must be at least one cycle in the prerequisites graph so we cannot complete all the courses.


  • 0
    I

    Thank you , I think I figure out, there might be multiple sink exist, not all the courses need to be on the same path.


  • 0
    B

    An interesting test case:

            /**
    Submission Result: Wrong Answer
    Input:  10, [[5,8],[3,5],[1,9],[4,5],[0,2],[1,9],[7,8],[4,9]]
    Output:     []
    Expected:   Special judge: No expected output available.
             */
    

    Please note there are two [1, 9] in the input, so you cannot just doing this:

        int[] inorder = new int[numCourses];
        for(int[] p: prerequisites){
            inorder[p[0]]++;
        }
    

    I ended up with a Set<Integer>[] preSets instead of the inorder array.


  • 0
    F

    Hi braydenCN. I noticed your point. That' why I put the "preVertex[prerequisites[i][1]]++;" statement in a if block to avoid repetition...


Log in to reply
 

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