LeetCode 210 - Course Schedule II

LeetCode 210 - Course Schedule II - 我的博客 - ITeye技术网站
Related: LeetCode 207 - Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

2, [[1,0]] There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1]

4, [[1,0],[2,0],[3,1],[3,2]] There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is[0,2,1,3].

1. This problem is equivalent to finding the topological order in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
2. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
3. Topological sort could also be done via BFS.

X. Topological Sort: BFS + In Degree 0
https://leetcode.com/problems/course-schedule-ii/discuss/59317/Two-AC-solution-in-Java-using-BFS-and-DFS-with-explanation

We observe that if a node has incoming edges, it has prerequisites. Therefore, the first few in the order must be those with no prerequisites, i.e. no incoming edges. Any non-empty DAG must have at least one node without incoming links. You can draw a small graph to convince yourself. If we visit these few and remove all edges attached to them, we are left with a smaller DAG, which is the same problem. This will then give our BFS solution.

private int[] solveByBFS(int[] incLinkCounts, List<List<Integer>> adjs){
    int[] order = new int[incLinkCounts.length];
    Queue<Integer> toVisit = new ArrayDeque<>();
    for (int i = 0; i < incLinkCounts.length; i++) {
        if (incLinkCounts[i] == 0) toVisit.offer(i);
    }
    int visited = 0;
    while (!toVisit.isEmpty()) {
        int from = toVisit.poll();
        order[visited++] = from;
        for (int to : adjs.get(from)) {
            incLinkCounts[to]--;
            if (incLinkCounts[to] == 0) toVisit.offer(to);
        }
    }
    return visited == incLinkCounts.length ? order : new int[0]; 
}https://leetcode.com/discuss/35568/standard-bfs-method-for-course-schedule-ii

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]; }
https://leetcode.com/discuss/36572/java-code-for-course-schedule-ii
public int[] findOrder(int numCourses, int[][] prerequisites) { if (numCourses <= 0) { return null; } int[] res = new int[numCourses]; int index = 0; if (prerequisites.length == 0 || prerequisites[0].length == 0) { while (index < numCourses) { res[index] = index++; } return res; } int[] course = new int[numCourses]; Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>(); for (int i = 0; i < prerequisites.length; i++) { int val = prerequisites[i][0]; int key = prerequisites[i][1]; if (!map.containsKey(key)) { map.put(key, new ArrayList<Integer>()); } map.get(key).add(val); course[val]++; } Queue<Integer> queue = new LinkedList<Integer>(); for (int i = 0; i < numCourses; i++) { if (course[i] == 0) { queue.add(i); res[index++] = i; } } while (!queue.isEmpty()) { int cur = queue.poll(); if (map.get(cur) != null) { for (int temp : map.get(cur)) { course[temp]--; if (course[temp] == 0) { queue.offer(temp); res[index++] = temp; } } } } for (int i = 0; i < numCourses; i++) { // this cab be improved if (course[i] != 0) { return new int[0]; } } return res; }
http://shibaili.blogspot.com/2015/06/day-107-minimum-size-subarray-sum.html
http://www.programcreek.com/2014/06/leetcode-course-schedule-ii-java/
http://likesky3.iteye.com/blog/2240473
http://blog.csdn.net/yano_nankai/article/details/50215365

只是加了一句话而已，用于保存结果。注意prerequisites为空的时候，任意输出一组结果即可。

public int[] findOrder(int numCourses, int[][] prerequisites) {
    if(prerequisites == null){
        throw new IllegalArgumentException("illegal prerequisites array");
    }
 
    int len = prerequisites.length;
 
    //if there is no prerequisites, return a sequence of courses
    if(len == 0){
        int[] res = new int[numCourses];
        for(int m=0; m<numCourses; m++){
            res[m]=m;
        }
        return res;
    }
 
    //records the number of prerequisites each course (0,...,numCourses-1) requires
    int[] pCounter = new int[numCourses];
    for(int i=0; i<len; i++){
        pCounter[prerequisites[i][0]]++;
    }
 
    //stores courses that have no prerequisites
    LinkedList<Integer> queue = new LinkedList<Integer>();
    for(int i=0; i<numCourses; i++){
        if(pCounter[i]==0){
            queue.add(i);
        }
    }
 
    int numNoPre = queue.size();
 
    //initialize result
    int[] result = new int[numCourses];
    int j=0;
 
    while(!queue.isEmpty()){
        int c = queue.remove();
        result[j++]=c;
 
        for(int i=0; i<len; i++){
            if(prerequisites[i][1]==c){
                pCounter[prerequisites[i][0]]--;
                if(pCounter[prerequisites[i][0]]==0){
                    queue.add(prerequisites[i][0]);
                    numNoPre++;
                }
            }
 
        }
    }
 
    //return result
    if(numNoPre==numCourses){
        return result;
    }else{
        return new int[0];
    }
}

http://blog.csdn.net/xudli/article/details/45912519

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] map = new int[numCourses];
        int n = prerequisites.length;
        int[] res = new int[numCourses];
        
        for(int i=0; i<n; i++) {
            map[ prerequisites[i][1] ] ++;
        }
        
        Queue<Integer> que = new LinkedList<Integer>();
        int index = numCourses-1;
        for(int i=0; i<numCourses; i++) {
            if(map[i] == 0) {
                que.add(i);
                res[index--] = i;
            }
        }
        
        while(!que.isEmpty() ){
            int k = que.remove();
            for(int i=0; i<n; i++) {
                int l = prerequisites[i][1];
                if(k==prerequisites[i][0]) {
                    map[l]--;
                    if(map[l] == 0) {
                        que.add(l);
                        res[index--] = l;
                    }
                }
            }
        }
        if(index!=-1) return new int[0];
        else return res;
    }

https://leetcode.com/discuss/85141/java-6ms-topological-sort-solution-with-explanation
public int[] findOrder(int numCourses, int[][] prerequisites) { int[] inDeg = new int[numCourses]; List<Integer>[] chl = new ArrayList[numCourses]; for (int i = 0; i < numCourses; i++) { chl[i] = new ArrayList<Integer>(); } int pre; int cour; for (int[] pair : prerequisites) { pre = pair[1]; cour = pair[0]; chl[pre].add(cour); inDeg[cour]++; } int[] res = new int[numCourses]; int k = 0; for (int i = 0; i < numCourses; i++) { if (inDeg[i] == 0) { res[k++] = i; } } if (k == 0) { return new int[0]; } int j = 0; List<Integer> tmp; while (k < numCourses) { tmp = chl[res[j++]]; for (int id : tmp) { if (--inDeg[id] == 0) { res[k++] = id; } } if (j == k) {//??\\ return new int[0]; } } return res; }
X. DFS + Topological Sort
https://leetcode.com/problems/course-schedule-ii/discuss/59342/Java-DFS-double-cache-visiting-each-vertex-once-433ms

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>(numCourses);
        for (int i = 0; i < numCourses; i++) adj.add(i, new ArrayList<>());
        for (int i = 0; i < prerequisites.length; i++) adj.get(prerequisites[i][1]).add(prerequisites[i][0]);
        boolean[] visited = new boolean[numCourses];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < numCourses; i++) {
            if (!topologicalSort(adj, i, stack, visited, new boolean[numCourses])) return new int[0];
        }
        int i = 0;
        int[] result = new int[numCourses];
        while (!stack.isEmpty()) {
            result[i++] = stack.pop();
        }
        return result;
    }
    
    private boolean topologicalSort(List<List<Integer>> adj, int v, Stack<Integer> stack, boolean[] visited, boolean[] isLoop) {
        if (visited[v]) return true;
        if (isLoop[v]) return false;
        isLoop[v] = true;
        for (Integer u : adj.get(v)) {
            if (!topologicalSort(adj, u, stack, visited, isLoop)) return false;
        }
        visited[v] = true;
        stack.push(v);
        return true;
    }




Another way to think about it is the last few in the order must be those which are not prerequisites of other courses. Thinking it recursively means if one node has unvisited child node, you should visit them first before you put this node down in the final order array. This sounds like the post-order of a DFS. Since we are putting nodes down in the reverse order, we should reverse it back to correct ordering or use a stack.

private int[] solveByDFS(List<List<Integer>> adjs) {
    BitSet hasCycle = new BitSet(1);
    BitSet visited = new BitSet(adjs.size());
    BitSet onStack = new BitSet(adjs.size());
    Deque<Integer> order = new ArrayDeque<>();
    for (int i = adjs.size() - 1; i >= 0; i--) {
        if (visited.get(i) == false && hasOrder(i, adjs, visited, onStack, order) == false) return new int[0];
    }
    int[] orderArray = new int[adjs.size()];
    for (int i = 0; !order.isEmpty(); i++) orderArray[i] = order.pop();
    return orderArray;
}

private boolean hasOrder(int from, List<List<Integer>> adjs, BitSet visited, BitSet onStack, Deque<Integer> order) {
    visited.set(from);
    onStack.set(from);
    for (int to : adjs.get(from)) {
        if (visited.get(to) == false) {
            if (hasOrder(to, adjs, visited, onStack, order) == false) return false;
        } else if (onStack.get(to) == true) {
            return false;
        }
    }
    onStack.clear(from);
    order.push(from);
    return true;
}

https://cheonhyangzhang.wordpress.com/2015/10/14/210-leetcode-java-course-schedule-ii-medium/

    int index = 0;

    public int[] findOrder(int numCourses, int[][] prerequisites) {

        HashMap<Integer, List<Integer>> adj = new HashMap<Integer, List<Integer>>();

        int n = numCourses;

        index = n - 1;

        int[][] pre = prerequisites;//make another reference to make variable name shorter

        int[] result = new int[n];

        initAdj(n, adj, pre);

        int[] color = new int[n];//0 white 1 gray 2 black

        for (int i = 0; i < n; i ++){

            if (!canFinishDFS(adj, color, result, i)){

                return new int[0];

            }

        }//for i

        return result;

    }

    private void initAdj(int n, HashMap<Integer, List<Integer>> adj, int[][] pre){

        for (int i = 0; i < n; i ++){

            adj.put(i, new LinkedList<Integer>());

        }

        for (int i = 0; i < pre.length; i ++){

            adj.get(pre[i][1]).add(pre[i][0]);

        }

    }

    private boolean canFinishDFS(HashMap<Integer, List<Integer>> adj, int[] color, int[] result, int i){

        if (color[i] == 1)

            return false;

        if (color[i] == 2)

            return true;

        color[i] = 1;

        for (Integer j:adj.get(i)){

            if (!canFinishDFS(adj, color, result, j)){

                return false;

            }

        }

        color[i] = 2;

        result[index] = i;

        index --;

        return true;

    }

1. vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {  
2.     vector<list<int>> adj(numCourses, list<int>());  
3.     vector<bool> visited(numCourses, false);  
4.     vector<bool> onstack(numCourses, false);  
5.     vector<int> order;  
6.       
7.     for(auto& it : prerequisites) {  
8.         adj[it.second].push_back(it.first);  
9.     }  
10.       
11.     for(int i=0; i<numCourses; ++i) {  
12.         if(visited[i]) continue;  
13.         if(hasCycle(adj, i, visited, onstack, order)) return vector<int>();  
14.     }  
15.     return order;  
16. }  
17.   
18. bool hasCycle(vector<list<int>>& adj, int v, vector<bool>& visited, vector<bool>& onstack, vector<int>& order) {  
19.     visited[v] = true;  
20.     onstack[v] = true;  
21.     for(auto& it : adj[v]) {  
22.         if(!visited[it] && hasCycle(adj, it, visited, onstack, order)) return true;  
23.         if(onstack[it]) return true;  
24.     }  
25.     order.insert(order.begin(), v);  
26.     onstack[v] = false;  
27.     return false;  
28. } 

topological sort, 考虑cycle问题
http://sgq626.blogspot.com/2015/07/leetcode-207leetcode-210-course.html
 topological sort DFS写法的一般思路： DFS+ mark visit III, 每次当一个点被mark成visited，之后将这个点加入rst中。
注意在用DFS + mark visit III之前，graph的表示是 course ->  pre-dependency,与判断directed graph里面有没有circle是相反的表示方式。

L ← Empty list that will contain the sorted nodes

for each of the node n in the graph do

visit(n)

function visit(node n)

if n is visited then return   

if n is visiting then stop (not a DAG, there is a cycle)

if n is not visited or visiting then

mark n visiting

                        for each node m which is n’s dependency do            

visit(m)        

      mark n visited        

      add n to head of L

    bool visit(int start, unordered_map<int, vector<int>> &gmap, int *M, vector<int> &rst) {
        //base case
        if (M[start] == 1) return true;
        if (M[start] == -1) return false; //cycle
        //mark
        M[start] = -1;//mark visiting
        for (int i = 0; i < gmap[start].size();i++) {
            if (visit(gmap[start][i], gmap, M, rst) == false) return false;
        }
        M[start] = 1; //visited
        rst.push_back(start);
        return true;
    }
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> rst;
        unordered_map<int, vector<int>> gmap;
        for (int i = 0; i < prerequisites.size(); i++) {
            gmap[prerequisites[i].first].push_back(prerequisites[i].second);
        }
        //vector<int> M(numCourses, 0);
        int M[numCourses] = {0};
        //for each node in the graph do visit n
        for (int i = 0; i < numCourses; i++) {
            if (visit(i, gmap, M, rst) == false) {
                rst.clear();
                break;
            }
        }
        return rst;
    }
https://leetcode.com/discuss/42710/java-dfs-double-cache-visiting-each-vertex-once-433ms
-- better to use int[] to cache
public int[] findOrder(int numCourses, int[][] prerequisites) { List<List<Integer>> adj = new ArrayList<>(numCourses); for (int i = 0; i < numCourses; i++) adj.add(i, new ArrayList<>()); for (int i = 0; i < prerequisites.length; i++) adj.get(prerequisites[i][1]).add(prerequisites[i][0]); boolean[] visited = new boolean[numCourses]; Stack<Integer> stack = new Stack<>(); for (int i = 0; i < numCourses; i++) { if (!topologicalSort(adj, i, stack, visited, new boolean[numCourses])) return new int[0]; } int i = 0; int[] result = new int[numCourses]; while (!stack.isEmpty()) { result[i++] = stack.pop(); } return result; } private boolean topologicalSort(List<List<Integer>> adj, int v, Stack<Integer> stack, boolean[] visited, boolean[] isLoop) { if (visited[v]) return true; if (isLoop[v]) return false; isLoop[v] = true; for (Integer u : adj.get(v)) { if (!topologicalSort(adj, u, stack, visited, isLoop)) return false; } visited[v] = true; stack.push(v); return true; }

https://leetcode.com/discuss/35605/two-ac-solution-in-java-using-bfs-and-dfs-with-explanation
Use BitSet
private int[] solveByDFS(List<List<Integer>> adjs) { BitSet hasCycle = new BitSet(1); BitSet visited = new BitSet(adjs.size()); BitSet onStack = new BitSet(adjs.size()); Deque<Integer> order = new ArrayDeque<>(); for (int i = adjs.size() - 1; i >= 0; i--) { if (visited.get(i) == false && hasOrder(i, adjs, visited, onStack, order) == false) return new int[0]; } int[] orderArray = new int[adjs.size()]; for (int i = 0; !order.isEmpty(); i++) orderArray[i] = order.pop(); return orderArray; } private boolean hasOrder(int from, List<List<Integer>> adjs, BitSet visited, BitSet onStack, Deque<Integer> order) { visited.set(from); onStack.set(from); for (int to : adjs.get(from)) { if (visited.get(to) == false) { if (hasOrder(to, adjs, visited, onStack, order) == false) return false; } else if (onStack.get(to) == true) { return false; } } onStack.clear(from); order.push(from); return true; }
http://shibaili.blogspot.com/2015/06/day-107-minimum-size-subarray-sum.html
Read full article from LeetCode 210 - Course Schedule II - 我的博客 - ITeye技术网站