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