Massive Algorithms: LeetCode 207- Course Schedule

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:

The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
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/45860195 http://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/

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，至于生成图的形式可以是邻接矩阵，也可以是邻接表。为了减小时间复杂度，本题考虑采用邻接表的方法。

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

// method 2: 二维数组表示有向图
public boolean canFinish2(int numCourses, int[][] prerequisites) {
if (prerequisites == null || prerequisites.length == 0 || prerequisites[0].length == 0)
return true;
// build graph
ArrayList<HashSet<Integer>> graph = new ArrayList<HashSet<Integer>>(numCourses);
int[] indegree = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
graph.add(new HashSet<Integer>());
}
int m = prerequisites.length;
for (int i = 0; i < m; i++) {
if (graph.get(prerequisites[i][1]).add(prerequisites[i][0]))
indegree[prerequisites[i][0]]++;
}
LinkedList<Integer> queue = new LinkedList<Integer>();
for (int i = 0; i < numCourses; i++) {
if (indegree[i] == 0) queue.offer(i);
}
int counter = 0;
while (!queue.isEmpty()) {
counter++;
int curr = queue.poll();
for (int w : graph.get(curr)) {
if (--indegree[w] == 0) queue.offer(w);
}
}
return counter == numCourses;
}
// method 1
class Vertex {
int value;
int indegree;
HashSet<Vertex> adjacent;
public Vertex(int val) {
this.value = val;
indegree = 0;
adjacent = new HashSet<Vertex>();
}
}
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (prerequisites == null || prerequisites.length == 0 || prerequisites[0].length == 0)
return true;
HashMap<Integer, Vertex> graph = buildGraph(numCourses, prerequisites);
LinkedList<Vertex> queue = new LinkedList<Vertex>();
for(Vertex node : graph.values()) {
if (node.indegree == 0)
queue.offer(node);
}
int counter = 0;
while (!queue.isEmpty()) {
Vertex node = queue.poll();
counter++;
for (Vertex w : node.adjacent) {
w.indegree--;
if (w.indegree == 0) queue.offer(w);
}
}
return counter == graph.size();
}
private HashMap<Integer, Vertex> buildGraph(int numCourses, int[][] prerequisites) {
HashMap<Integer, Vertex> graph = new HashMap<Integer, Vertex>();
for (int i = 0; i < numCourses; i++) {
graph.put(i, new Vertex(i));
}
int m = prerequisites.length;
for (int i = 0; i < m; i++) {
if(graph.get(prerequisites[i][1]).adjacent.add(graph.get(prerequisites[i][0]))) {
graph.get(prerequisites[i][0]).indegree++;
}
}
return graph;
}

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

LeetCode 207- Course Schedule

Labels

Popular Posts