Course Schedule

Graph, Depth-first Search, Breadth-first Search, Topological Sorting

Medium

There are a total of n courses you have to take, labeled from0ton-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.

Analysis

此题考虑课程依赖关系是否能满足，其实抽象来看，课程的依赖关系其实是有向图的边edge，那么问题的内核其实就是这个有向图是否有环，如果无环，则依赖关系可以成立，也就是DAG （有向无环图）。判定是否为DAG，则可以用拓扑排序Topological Sorting。

https://www.youtube.com/watch?v=M6SBePBMznU

拓扑排序 = 顶点染色 + 记录顺序

这里只需要顶点染色即可。

DFS - 需要先遍历叶子节点，再遍历根节点，因此可以看成是post-order

Solution

Topological Sorting - HashMap - DFS - (9ms 83.11% AC)

class Solution {
    private HashMap<Integer, ArrayList<Integer>> graph;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
         graph = new HashMap<Integer, ArrayList<Integer>>();   
         // states: 0 = unknown, 1 = visiting, 2 = visited
         int[] visit = new int[numCourses];
         for (int i = 0; i < numCourses; i++) {
             graph.put(i, new ArrayList<Integer>());
         }
         for (int[] p : prerequisites) {
             if (graph.containsKey(p[0])) {
                graph.get(p[0]).add(p[1]);
             } 
         } 
         for (int i = 0; i < numCourses; i++) {
             if (dfs(i, visit)) return false;
         }
        return true;
    }

    private boolean dfs(int cur, int[] v) {
        if (v[cur] == 1) return true;
        if (v[cur] == 2) return false;

        v[cur] = 1;
        for (int i = 0; i < graph.get(cur).size(); i++) {
            if (dfs(graph.get(cur).get(i), v)) return true;
        } 

        v[cur] = 2;
        return false;
    }
}

*Topological Sort - DFS - Improved - ArrayList[] - (5ms 99.81% AC)

class Solution {
    private ArrayList[] graph;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        graph = new ArrayList [numCourses];
        // states: 0 = unknown, 1 = visiting, 2 = visited
        int[] visit = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList < Integer > ();
        }
        for (int[] p: prerequisites) {
            graph[p[0]].add(p[1]);
        }
        for (int i = 0; i < numCourses; i++) {
            if (dfsCyclic(i, visit)) return false;
        }
        return true;
    }
    private boolean dfsCyclic(int cur, int[] v) {
        if (v[cur] == 1) return true;
        if (v[cur] == 2) return false;
        v[cur] = 1;
        for (int i = 0; i < graph[cur].size(); i++) {
            if (dfsCyclic((int) graph[cur].get(i), v)) return true;
        }
        v[cur] = 2;
        return false;
    }
}

Topological Sort - OO Style - DFS (8ms 87.81% AC)

Modified from https://leetcode.com/problems/course-schedule/discuss/58713/OO-easy-to-read-java-solution

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Course[] courses = new Course[numCourses];
        for (int i = 0; i < numCourses; i++) {
            courses[i] = new Course();
        }
        for (int i = 0; i < prerequisites.length; i++) {
            courses[prerequisites[i][0]].add(courses[prerequisites[i][1]]);
        }
        for (int i = 0; i < numCourses; i++) {
            if (isCyclic(courses[i])) return false;
        }
        return true;
    }

    private boolean isCyclic(Course cur) {
        if (cur.tested) return false;
        if (cur.visited) return true;
        cur.visited = true;
        for (Course c: cur.pre) {
            if (isCyclic(c)) {
                return true;
            }
        }
        cur.tested = true;
        return false;
    }

    class Course {
        boolean visited = false; // being visited
        boolean tested = false; // tested if cyclic
        List < Course > pre = new ArrayList < Course > ();
        public void add(Course c) {
            pre.add(c);
        }
    }
}

BFS

public class Solution {
    /**
     * @param numCourses a total of n courses
     * @param prerequisites a list of prerequisite pairs
     * @return true if can finish all courses or false
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // Write your code here
        List[] edges = new ArrayList[numCourses];
        int[] degree = new int[numCourses];

        for (int i = 0;i < numCourses; i++)
            edges[i] = new ArrayList<Integer>();

        for (int i = 0; i < prerequisites.length; i++) {
            degree[prerequisites[i][0]] ++ ;
            edges[prerequisites[i][1]].add(prerequisites[i][0]);
        }

        Queue queue = new LinkedList();
        for(int i = 0; i < degree.length; i++){
            if (degree[i] == 0) {
                queue.add(i);
            }
        }

        int count = 0;
        while(!queue.isEmpty()){
            int course = (int)queue.poll();
            count ++;
            int n = edges[course].size();
            for(int i = 0; i < n; i++){
                int pointer = (int)edges[course].get(i);
                degree[pointer]--;
                if (degree[pointer] == 0) {
                    queue.add(pointer);
                }
            }
        }

        return count == numCourses;
    }
}

Reference

https://www.jiuzhang.com/solution/course-schedule

https://blog.csdn.net/ljiabin/article/details/45846837

https://www.youtube.com/watch?v=ddTC4Zovtbc