207. Course Schedule.md

Solution1

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        int[] indegree = new int[numCourses];
        int count = 0;
        
        for (int i = 0; i < prerequisites.length; i++) {
            int pre = prerequisites[i][1];
            int cur = prerequisites[i][0];
            indegree[cur]++;
            Set<Integer> set = new HashSet<>();
            if (map.containsKey(pre)) {
                set = map.get(pre);
                set.add(cur);
                map.put(pre, set);
            }
            if (!set.contains(cur)) {
                set.add(cur);
                map.put(pre, set);
            }
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            int pre = queue.poll();
            count++;
            if (map.containsKey(pre)) {
                for (int cur : map.get(pre)) {
                    if (--indegree[cur] == 0) {
                        queue.offer(cur);
                    }
                }
            }
            
        }
        return count == numCourses;
    }
}

note

• Similar to the Course Schedule 2 but just return true or false. The idea is to do a bfs topological sorting to detect if there's cycle in the graph which will result in the final count not equal to numCourses.
• Be careful in the final while loop when polling from queue, not all polled course is in hashmap because some classes might not have following classes, so need to check if map contains it.
• Empty prerequiste is considered true.