LeetCode 207- Course Schedule

Leetcode207-Course Schedule – Hu Haoyu's Blog – Learn and live

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, is it possible for you to finish all courses?

Example 1:

Input: 2, [[1,0]] 
Output: true
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: 2, [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
             To take course 1 you should have finished course 0, and to take course 0 you should
             also have finished course 1. So it is impossible.

Note:

1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
2. You may assume that there are no duplicate edges in the input prerequisites

X. Topological Sort
https://leetcode.com/problems/course-schedule/discuss/58516/Easy-BFS-Topological-sort-Java

public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[][] matrix = new int[numCourses][numCourses]; // i -> j
    int[] indegree = new int[numCourses];
    
    for (int i=0; i<prerequisites.length; i++) {
        int ready = prerequisites[i][0];
        int pre = prerequisites[i][1];
        if (matrix[pre][ready] == 0)
            indegree[ready]++; //duplicate case
        matrix[pre][ready] = 1;
    }
    
    int count = 0;
    Queue<Integer> queue = new LinkedList();
    for (int i=0; i<indegree.length; i++) {
        if (indegree[i] == 0) queue.offer(i);
    }
    while (!queue.isEmpty()) {
        int course = queue.poll();
        count++;
        for (int i=0; i<numCourses; i++) {
            if (matrix[course][i] != 0) {
                if (--indegree[i] == 0)
                    queue.offer(i);
            }
        }
    }
    return count == numCourses;
}

https://discuss.leetcode.com/topic/35278/java-easy-version-to-understand

http://blog.csdn.net/xudli/article/details/45860195http://www.programcreek.com/2014/05/leetcode-course-schedule-java/

使用topological sorting, 成功sort后,如果prerequisite没有空,则没有环.

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

https://discuss.leetcode.com/topic/13854/easy-bfs-topological-sort-java
http://tengfei.tech/2016/05/28/Leetcode-207-Course-Schedule/

1 2 3 4 5 6 7 8 9 10 11 12 13

L ← Empty list that will contain the sorted elements S ← Set of all nodes with no incoming edges while S is non-empty do remove a node n from S add n to tail of L for each node m with an edge e from n to m do remove edge e from the graph if m has no other incoming edges then insert m into S if graph has edges then return error (graph has at least one cycle) else return L (a topologically sorted order)

public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[][] matrix = new int[numCourses][numCourses]; // i -> j
    int[] indegree = new int[numCourses];
    
    for (int i=0; i<prerequisites.length; i++) {
        int ready = prerequisites[i][0];
        int pre = prerequisites[i][1];
        if (matrix[pre][ready] == 0)
            indegree[ready]++; //duplicate case
        matrix[pre][ready] = 1;
    }
    
    int count = 0;
    Queue<Integer> queue = new LinkedList();
    for (int i=0; i<indegree.length; i++) {
        if (indegree[i] == 0) queue.offer(i);
    }
    while (!queue.isEmpty()) {
        int course = queue.poll();
        count++;
        for (int i=0; i<numCourses; i++) {
            if (matrix[course][i] != 0) {
                if (--indegree[i] == 0)
                    queue.offer(i);
            }
        }
    }
    return count == numCourses;
}

X. DFS - check circle

很显然，这是一个有向无环图的判断问题。只要所有课程中出现了环，就不可能修满所有课程。有向无环图的判断可采用dfs或bfs，至于生成图的形式可以是邻接矩阵，也可以是邻接表。为了减小时间复杂度，本题考虑采用邻接表的方法。

1. 将每个先后修要求对导入邻接表中。
2. 将使用dfs判断是否无环：
   2.1 用isVisited记录各个课程是否被访问过；
   2.2 用onStack记录一条路径上的课程，判断是否有环；
   2.3 有环返回true，无环继续；
3. 如有环主函数返回false，否则返回true。

https://leetcode.com/problems/course-schedule/discuss/58524/Java-DFS-and-BFS-solution

        public boolean canFinish(int numCourses, int[][] prerequisites) {
            ArrayList[] graph = new ArrayList[numCourses];
            for(int i=0;i<numCourses;i++)
                graph[i] = new ArrayList();
                
            boolean[] visited = new boolean[numCourses];
            for(int i=0; i<prerequisites.length;i++){
                graph[prerequisites[i][1]].add(prerequisites[i][0]);
            }

            for(int i=0; i<numCourses; i++){
                if(!dfs(graph,visited,i))
                    return false;
            }
            return true;
        }

        private boolean dfs(ArrayList[] graph, boolean[] visited, int course){
            if(visited[course])
                return false;
            else
                visited[course] = true;;

            for(int i=0; i<graph[course].size();i++){
                if(!dfs(graph,visited,(int)graph[course].get(i)))
                    return false;
            }
            visited[course] = false;
            return true;
        }




http://www.programcreek.com/2014/05/leetcode-course-schedule-java/

public boolean canFinish(int numCourses, int[][] prerequisites) {
    if(prerequisites == null){
        throw new IllegalArgumentException("illegal prerequisites array");
    }
 
    int len = prerequisites.length;
 
    if(numCourses == 0 || len == 0){
        return true;
    }
 
    //track visited courses
    int[] visit = new int[numCourses];
 
    // use the map to store what courses depend on a course 
    HashMap<Integer,ArrayList<Integer>> map = new HashMap<Integer,ArrayList<Integer>>();
    for(int[] a: prerequisites){
        if(map.containsKey(a[1])){
            map.get(a[1]).add(a[0]);
        }else{
            ArrayList<Integer> l = new ArrayList<Integer>();
            l.add(a[0]);
            map.put(a[1], l);
        }
    }
 
    for(int i=0; i<numCourses; i++){
        if(!canFinishDFS(map, visit, i))
            return false;
    }
 
    return true;
}
 
private boolean canFinishDFS(HashMap<Integer,ArrayList<Integer>> map, int[] visit, int i){
    if(visit[i]==-1) 
        return false;
    if(visit[i]==1) 
        return true;
 
    visit[i]=-1;
    if(map.containsKey(i)){
        for(int j: map.get(i)){
            if(!canFinishDFS(map, visit, j)) 
                return false;
        }
    }
 
    visit[i]=1;
 
    return true;
}

    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        if (!prerequisites.size()) return true;
        vector<vector<int>> map(numCourses, vector<int>());
        for (int i = 0; i < prerequisites.size(); ++i) {
            map[prerequisites[i][0]].push_back(prerequisites[i][1]);
        }
        vector<bool> isVisited(numCourses, false);
        for (int i = 0; i < numCourses; ++i) {
            if (!isVisited[i]) {
                vector<bool> onStack(numCourses, false);
                if (hasCycle(map, i, isVisited, onStack))
                    return false;
            }
        }
        return true;
    }
    bool hasCycle(vector<vector<int>> &map, int i, vector<bool> &isVisited, vector<bool> &onStack) {
        isVisited[i] = true;
        onStack[i] = true;
        for (int k : map[i]) {
            if (onStack[k])
                return true;
            else
                if (hasCycle(map, k, isVisited, onStack))
                    return true;
        }
        onStack[i] = false;
        return false;
    }

https://leijiangcoding.wordpress.com/2015/05/06/leetcode-q207-course-schedule/
http://likesky3.iteye.com/blog/2240465
网上搜了搜逆拓扑，发现其是有可用之处的，参见下面这篇博文： 
http://blog.csdn.net/guodongxiaren/article/details/37988833 
另一篇博文提出拓扑排序是所有节点dfs的逆后序，也就是每个节点任务完成的时间的逆序排序 ，这个洞见也挺有意思的https://m.oschina.net/blog/419291 

1.    // method 2: 二维数组表示有向图  
2.     public boolean canFinish2(int numCourses, int[][] prerequisites) {  
3.         if (prerequisites == null || prerequisites.length == 0 || prerequisites[0].length == 0)  
4.             return true;  
5.         // build graph  
6.         ArrayList<HashSet<Integer>> graph = new ArrayList<HashSet<Integer>>(numCourses);  
7.         int[] indegree = new int[numCourses];  
8.         for (int i = 0; i < numCourses; i++) {  
9.             graph.add(new HashSet<Integer>());  
10.         }  
11.         int m = prerequisites.length;  
12.         for (int i = 0; i < m; i++) {  
13.             if (graph.get(prerequisites[i][1]).add(prerequisites[i][0]))  
14.                 indegree[prerequisites[i][0]]++;  
15.         }  
16.         LinkedList<Integer> queue = new LinkedList<Integer>();  
17.         for (int i = 0; i < numCourses; i++) {  
18.             if (indegree[i] == 0) queue.offer(i);  
19.         }  
20.         int counter = 0;  
21.         while (!queue.isEmpty()) {  
22.             counter++;  
23.             int curr = queue.poll();  
24.             for (int w : graph.get(curr)) {  
25.                 if (--indegree[w] == 0) queue.offer(w);  
26.             }  
27.         }  
28.         return counter == numCourses;  
29.     }  
30.     // method 1  
31.     class Vertex {  
32.         int value;  
33.         int indegree;  
34.         HashSet<Vertex> adjacent;  
35.         public Vertex(int val) {  
36.             this.value = val;  
37.             indegree = 0;  
38.             adjacent = new HashSet<Vertex>();  
39.         }  
40.     }  
41.     public boolean canFinish(int numCourses, int[][] prerequisites) {  
42.         if (prerequisites == null || prerequisites.length == 0 || prerequisites[0].length == 0)  
43.             return true;  
44.         HashMap<Integer, Vertex> graph = buildGraph(numCourses, prerequisites);  
45.         LinkedList<Vertex> queue = new LinkedList<Vertex>();  
46.         for(Vertex node : graph.values()) {  
47.             if (node.indegree == 0)  
48.                 queue.offer(node);  
49.         }  
50.         int counter = 0;  
51.         while (!queue.isEmpty()) {  
52.             Vertex node = queue.poll();  
53.             counter++;  
54.             for (Vertex w : node.adjacent) {  
55.                 w.indegree--;  
56.                 if (w.indegree == 0) queue.offer(w);  
57.             }  
58.         }  
59.         return counter == graph.size();  
60.     }  
61.     private HashMap<Integer, Vertex> buildGraph(int numCourses, int[][] prerequisites) {  
62.         HashMap<Integer, Vertex> graph = new HashMap<Integer, Vertex>();  
63.         for (int i = 0; i < numCourses; i++) {  
64.             graph.put(i, new Vertex(i));  
65.         }  
66.         int m = prerequisites.length;  
67.         for (int i = 0; i < m; i++) {  
68.             if(graph.get(prerequisites[i][1]).adjacent.add(graph.get(prerequisites[i][0]))) {  
69.                 graph.get(prerequisites[i][0]).indegree++;  
70.             }  
71.         }  
72.         return graph;  
73.     }  

Read full article from Leetcode207-Course Schedule – Hu Haoyu's Blog – Learn and live