Course Schedule

Java

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (prerequisites == null || prerequisites.length == 0 || numCourses == 0) {
            return true;
        }
        int[] inDegree = getInDegree(numCourses, prerequisites);
        Map<Integer, List<Integer>> dependencies = getDependencies(prerequisites);
        int selectedCourse = 0;
        
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        while (!queue.isEmpty()) {
            int course = queue.poll();
            selectedCourse++;
            if (!dependencies.containsKey(course)) {
                continue;
            }
            
            for (int related : dependencies.get(course)) {
                inDegree[related]--;
                if (inDegree[related] == 0) {
                    queue.offer(related);
                }
            }
        }
        
        return selectedCourse == numCourses;
    }
    
    private int[] getInDegree(int numCourses, int[][] prerequisites) {
        int[] inDegree = new int[numCourses];
        for (int[] prerequisite : prerequisites) {
            inDegree[prerequisite[0]]++;
        }
        return inDegree;
    }
    
    private Map<Integer, List<Integer>> getDependencies(int[][] prerequisites) {
        Map<Integer, List<Integer>> dependencies = new HashMap<>();
        for (int[] prerequisite : prerequisites) {
         dependencies.putIfAbsent(prerequisite[1], new ArrayList<>());
         dependencies.get(prerequisite[1]).add(prerequisite[0]);
        }
        return dependencies;
    }
}

Python

from collections import deque
from collections import defaultdict
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        todo = {i: set() for i in range(numCourses)} 
        graph = defaultdict(set)
        for i,j in prerequisites:
            todo[i].add(j)
            graph[j].add(i)
        q = deque([])
        for k,v in todo.items():
            if len(v) == 0:
                q.append(k)
        while q:
            n = q.popleft()
            for i in graph[n]:
                todo[i].remove(n)
                if len(todo[i]) == 0:
                    q.append(i)
            todo.pop(n)
        return not todo

JavaScript

var canFinish = function(numCourses, prerequisites) {
    const map = {};
    const inDegree = new Array(numCourses);
    inDegree.fill(0);
    for (const pre of prerequisites) {
        inDegree[pre[0]]++;
        map[pre[1]] = map[pre[1]] || [];
        map[pre[1]].push(pre[0]);
    }
    
    const queue = [];
    for (let i = 0; i < numCourses; i++) {
        if (!inDegree[i]) {
            queue.push(i);
        }
    }
    while (queue.length) {
        const course = queue.shift();
        numCourses--;
        if (map[course]) {
            for (const related of map[course]) {
                inDegree[related]--;
                if (!inDegree[related]) {
                    queue.push(related);
                }
            }
        }
    }
    return !numCourses;
};