# 207&210. Course Schedule I\&II

207。Course Schedule I

There are a total of `numCourses` courses you have to take, labeled from `0` to `numCourses - 1`. You are given an array `prerequisites` where `prerequisites[i] = [ai, bi]` indicates that you **must** take course `bi` first if you want to take course `ai`.

* For example, the pair `[0, 1]`, indicates that to take course `0` you have to first take course `1`.

Return `true` if you can finish all courses. Otherwise, return `false`.

**Example 1:**

<pre><code><strong>Input: numCourses = 2, prerequisites = [[1,0]]
</strong><strong>Output: true
</strong><strong>Explanation: There are a total of 2 courses to take. 
</strong>To take course 1 you should have finished course 0. So it is possible.
</code></pre>

**Example 2:**

<pre><code><strong>Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
</strong><strong>Output: false
</strong><strong>Explanation: There are a total of 2 courses to take. 
</strong>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.
</code></pre>

**Constraints:**

* `1 <= numCourses <= 2000`
* `0 <= prerequisites.length <= 5000`
* `prerequisites[i].length == 2`
* `0 <= ai, bi < numCourses`
* All the pairs prerequisites\[i] are **unique**.

***My Solutions:***

用一个visited\[]数组，记录每一个节点的状态。其中visited\[i]的值：0 代表还未访问的状态; 1 代表正在访问的状态; 2 代表已经访问完成。&#x20;

如果当前访问节点的状态为1，说明该节点正在递归访问其后续节点，此时再次回到当前节点时，只能说明递归访问路径出现了环路（比如课程A的先修课是B，此时A的状态为1，递归到B时发现其先修课为A，再递归到A时发现其状态为1，这就是回路。），这是不能满足条件的情况，可以直接返回false。

一门课程C，其先修课为A，如果A的转态是2，说明已经访问过A，并且没有回路

```java
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {

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

        // 将prereq转化为图结构，每门课在graph的一个格子里，每个格子有一个list，list里加入需要的先修课程
        for (int[] prereq : prerequisites) graph[prereq[0]].add(prereq[1]);

        int[] visited = new int[numCourses];

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

    // 如果没有回路，返回true；如果有回路，返回false
    private boolean dfs(List<Integer>[] graph, int i, int[] visited) {
        if (visited[i] == 1) return false; 
        if (visited[i] == 2) return true;
        visited[i] = 1; // 开始递归当前节点的先修课, 将状态更新为1
        for (int pre : graph[i]) {
            // 递归查看先修课之后的路径是否有回路
            if (!dfs(graph, pre, visited)) return false;
        }
        // 当前节点的所有先修课路径循环结束后，将visited更新为2。
        visited[i] = 2;
        return true;
    }
}
```

**210。Course Schedule II**

There are a total of `numCourses` courses you have to take, labeled from `0` to `numCourses - 1`. You are given an array `prerequisites` where `prerequisites[i] = [ai, bi]` indicates that you **must** take course `bi` first if you want to take course `ai`.

* For example, the pair `[0, 1]`, indicates that to take course `0` you have to first take course `1`.

Return *the ordering of courses you should take to finish all courses*. If there are many valid answers, return **any** of them. If it is impossible to finish all courses, return **an empty array**.

**Example 1:**

<pre><code><strong>Input: numCourses = 2, prerequisites = [[1,0]]
</strong><strong>Output: [0,1]
</strong><strong>Explanation: 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].
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
</strong><strong>Output: [0,2,1,3]
</strong><strong>Explanation: 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.
</strong>So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].
</code></pre>

**Example 3:**

<pre><code><strong>Input: numCourses = 1, prerequisites = []
</strong><strong>Output: [0]
</strong></code></pre>

和上题类似，但要返回先修课程

***My Solutions:***

解法和上题类似，但因为要返回先修课程，需要在dfs的时候加入一个list，在每判断完一个节点和将visited数组更新为2时，把这个点加入到返回的list中。

```java
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = new ArrayList[numCourses];
        for (int i = 0; i <numCourses; i++) {
            graph[i] = new ArrayList<>();
        }
        
        for (int[] prereq : prerequisites) {
            graph[prereq[0]].add(prereq[1]);
        }

        int[] visited = new int[numCourses];
        
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(graph, i, visited, list)) return new int[0]; // return empty array if cannot finish courses
        }
        
        int[] res = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    // 注意这里传入了一个list，用来储存dfs路上的节点
    private boolean dfs(List<Integer>[] graph, int i, int[] visited, List<Integer> list) {
        if (visited[i] == 1) return false;
        if (visited[i] == 2) return true;
        visited[i] = 1;
        for (int pre : graph[i]) {
            if (!dfs(graph, pre, visited, list)) return false;
        }
        visited[i] = 2;
        // 需要在判断完每一个节点后（将visited更新为2的时间点）将其加入到返回list中
        list.add(i);
        return true;
    }
}
```

dfs可能造成stack overflow. 用bfs这样写

```java
public class Solution {
    /*
     * @param numCourses: a total of n courses
     * @param prerequisites: a list of prerequisite pairs
     * @return: the course order
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // write your code here
        if (prerequisites == null || prerequisites.length == 0 || prerequisites[0].length == 0) {
            int[] ans = new int[numCourses];
            for (int i = 0; i < numCourses; i++) ans[i] = i;
            return ans;
        }
        
        // build up a map for prerequisites
        Map<Integer, List<Integer>> courseMap = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            courseMap.put(i, new ArrayList<Integer>());
        }
        for (int i = 0; i < prerequisites.length; i++) {
            int cur = prerequisites[i][0];
            int nei = prerequisites[i][1];
            courseMap.get(cur).add(nei);
        }
        
        // topological sorting
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            // 在map里记录被当成prerequisite的课程号和ta被当做prereq的次数
            for (Integer neighbor : courseMap.get(i)) {
                map.put(neighbor, map.getOrDefault(neighbor, 0) + 1);
            }
        }

        List<Integer> result = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (!map.containsKey(i)) { // 只有不是prereq的课才能被加入q
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            Integer course = queue.poll();
            result.add(course);
            for (Integer neighbor : courseMap.get(course)) {
                if (map.containsKey(neighbor)) {
                    map.put(neighbor, map.get(neighbor) - 1);
                } 
                if (map.get(neighbor) == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        
        // convert ArrayList to int[] 
        if (result.size() == numCourses) {
            int[] ans = new int[numCourses];
            for (int i = 0; i < result.size(); i++) {
                // 因为是没有prereq的课被先加到result里面去，所以这里顺序要相反
                ans[i] = result.get(result.size() - 1 - i);
            }
            return ans;
        } else return new int[0];
    }
}
```
