# Course Schedule

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

**Medium**

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](https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs).
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)**

```java
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)**

```java
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)**&#x20;

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

```java
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**

```java
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>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/graph_search/course-schedule.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.