207. Course Schedule

https://leetcode.com/problems/course-schedule/

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // prerequisite -> courses it influences
        Map<Integer, Set<Integer>> map = new HashMap<>();
        int[] indegrees = new int[numCourses];
        for (int[] pre : prerequisites) {
            int first = pre[1];
            int second = pre[0];
            Set<Integer> courses = map.get(first);
            indegrees[second]++;
            if (courses == null) {
                courses = new HashSet<>();
            }
            courses.add(second);
            map.put(first, courses);
        }
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegrees[i] == 0) {
                queue.offer(i);
            }
        }
        int taken = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            taken++;
            // visited.add(course);
            Set<Integer> courses = map.get(course);
            if (courses == null) {
                continue;
            }
            for (int c : courses) {
                indegrees[c]--;
                if (indegrees[c] == 0) {
                    queue.offer(c);
                }
            }
        }
        return taken == numCourses;
    }
}

注意判断条件是能上的课的数量等于课的总数量，而且拓扑排序不需要visited