Course Schedule 08/03

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?Have you met this question in a real interview? Yes

Example

Given n = 2, prerequisites = [[1,0]] Return true

Given n = 2, prerequisites = [[1,0],[0,1]] Return false

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
        // 已知node和edge构造存储有向图图的map
        // 有了map之后，剩下的解法类似于topological sorting 那道题
        // 思路：1.把输入的参数转换成map形式存储的图
        // 2.拓扑排序得到list of result
        // 3.判断list中的节点个数是否为numCourses
        // 因为拓扑排序节点入度为0时才会存入result
        // 所以如果存在环，那么有向图的拓扑排序节点个数就会小于图的节点个数
        if (numCourses == 0 || prerequisites.length == 0) {
            return true;
        }
        
        //创建courseMap
        HashMap<Integer, List<Integer>> courseMap = creatCourseMap(numCourses, prerequisites);
        //统计各个节点的入度
        HashMap<Integer, Integer> indegreeMap = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            for (Integer neighbor : courseMap.get(i)) {
                if (indegreeMap.containsKey(neighbor)) {
                    indegreeMap.put(neighbor, indegreeMap.get(neighbor) + 1);
                } else {
                    indegreeMap.put(neighbor, 1);
                }
            }
        }
        
        // 把所有入度为0的点，放到BFS专用的队列中
        Queue<Integer> queue = new LinkedList<>();
        // 初始化拓扑序列为空
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            if (!indegreeMap.containsKey(i)) {
                queue.offer(i);
                result.add(i);
            }
        }
        
        // 每次从队列中拿出一个点放到拓扑序列里，并将该点指向的所有点的入度减1
        while (!queue.isEmpty()) {
            Integer course = queue.poll();
            for (Integer neighbor : courseMap.get(course)) {
                indegreeMap.put(neighbor, indegreeMap.get(neighbor) - 1);
                // 减去1之后入度变为0的点，也放入队列
                if (indegreeMap.get(neighbor) == 0) {
                    queue.offer(neighbor);
                    result.add(neighbor);
                }
            }
        }
        // 判断拓扑排序数与图的节点数是否相同
        return result.size() == numCourses;
    }
    
    //创建courseMap有向图,方向为先修课程指向当前课程pre -> sou
    private HashMap<Integer, List<Integer>> creatCourseMap(int numCourses, int[][] prerequisites) {
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            map.put(i, new ArrayList<>());
        }
        for (int i = 0; i < prerequisites.length; i++) {
            int cur = prerequisites[i][0];
            int pre = prerequisites[i][1];
            map.get(pre).add(cur);
        }
        return map;
    }
}