Problem #207: Course Schedule

Intuition & Strategy Breakdown

Use Topological Sort (Kahn's Algorithm with in-degrees or DFS cycle detection). Return true if graph contains no directed cycle.

Python Solution

from collections import deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        adj = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses
        
        for crs, pre in prerequisites:
            adj[pre].append(crs)
            indegree[crs] += 1
            
        q = deque([i for i in range(numCourses) if indegree[i] == 0])
        count = 0
        
        while q:
            crs = q.popleft()
            count += 1
            
            for neighbor in adj[crs]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    q.append(neighbor)
                    
        return count == numCourses

Java Solution

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
        int[] indegree = new int[numCourses];
        
        for (int[] pre : prerequisites) {
            adj.get(pre[1]).add(pre[0]);
            indegree[pre[0]]++;
        }
        
        Queue q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) q.add(i);
        }
        
        int count = 0;
        while (!q.isEmpty()) {
            int crs = q.poll();
            count++;
            for (int neighbor : adj.get(crs)) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) q.add(neighbor);
            }
        }
        
        return count == numCourses;
    }
}