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:

Input: numCourses = 2, prerequisites = [[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: numCourses = 2, prerequisites = [[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.

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 代表已经访问完成。

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

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

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:

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

Example 2:

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

Example 3:

Input: numCourses = 1, prerequisites = []
Output: [0]

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

My Solutions:

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

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这样写

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];
    }
}