Course Schedule — Topological Sort BFS (Kahns Algorithm)

# Python — Kahn's BFS
from collections import defaultdict, deque
def canFinish(numCourses, prerequisites):
    in_degree = [0]*numCourses
    graph = defaultdict(list)
    for a, b in prerequisites:
        graph[b].append(a); in_degree[a] += 1
    queue = deque(i for i in range(numCourses) if in_degree[i]==0)
    completed = 0
    while queue:
        node = queue.popleft(); completed += 1
        for nei in graph[node]:
            in_degree[nei] -= 1
            if in_degree[nei] == 0: queue.append(nei)
    return completed == numCourses

// Java
public boolean canFinish(int n, int[][] prereqs) {
    int[] inDeg = new int[n];
    List<List<Integer>> graph = new ArrayList<>();
    for (int i=0;i<n;i++) graph.add(new ArrayList<>());
    for (int[] p : prereqs) { graph.get(p[1]).add(p[0]); inDeg[p[0]]++; }
    Queue<Integer> q = new LinkedList<>();
    for (int i=0;i<n;i++) if (inDeg[i]==0) q.offer(i);
    int done = 0;
    while (!q.isEmpty()) {
        int node = q.poll(); done++;
        for (int nei : graph.get(node)) if (--inDeg[nei]==0) q.offer(nei);
    }
    return done==n;
}