LeetCode(210) -- Course Schedule II

Problem

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, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: 2, [[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: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [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] .

My Solution

用DFS做topilogical sort，参照了269题，用seen表示三种状态：没有这个key，代表这个节点从未访问过，白色；有key,但是value是false, 代表当前节点访问过，但它的子节点还没完成访问，灰色；有key，同时为true，代表完成了该节点及其所有子节点，黑色。

另外，下面的map其实是反向的图，跟平时理解的前置课程箭头方向相反。比如，课程1的前置课是课程2，正常的理解应该是先上2，再上1，所以箭头从2指向1。但是这里我们把箭头完全调转了方向，从1指向2。这样的好处是，当一个节点没有子节点时，也就代表它没有前置课了，也就是dfs中的叶节点了，也就是说此时我们就可以把它放入到最终结果了。这样就省去了做top sort时最后再反转的那一步，也不需要用stack了。

class Solution {
    
    Map<Integer, Boolean> seen = new HashMap<>();
    List<Integer> ans = new ArrayList<>();
    Map<Integer, List<Integer>> map = new HashMap<>();
    
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        
        for (int i = 0; i < numCourses; i++) {
            map.put(i, new ArrayList<Integer>());
        }
        for (int[] pair : prerequisites) {
            map.get(pair[0]).add(pair[1]);
        }
        
        for (int i = 0; i < numCourses; i++) {
            boolean result = dfs(i);
            if (!result) {
                return new int[0];
            }
        }
        int[] res = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            res[i] = ans.get(i);
        }
        return res;
        
    }
    
    private boolean dfs(int course) {
        if (seen.containsKey(course)) {
            return seen.get(course);
        }
        seen.put(course, false);
        for (int next : map.get(course)) {
            boolean result = dfs(next);
            if (!result) return false;
        }
        seen.put(course, true);
        ans.add(course);
        return true;
    }
}