MediumGraphs

Course Schedule

graphtopological-sortdfscycle-detection

Problem

There are numCourses courses labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a, b] indicates you must take course b before course a.

Return true if you can finish all courses (no cycle), false otherwise.

Examples

Example 1

Input: numCourses = 2, prerequisites = [[1,0]]

Output: true

Explanation: Take 0 then 1.

Example 2

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]

Output: false

Explanation: Cycle: 0→1→0.

Constraints

•1 <= numCourses <= 2000
•0 <= prerequisites.length <= 5000

Hints

Hint 1

Topological sort with Kahn's algorithm (BFS). If all nodes are processed, no cycle exists.

Solutions

public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[] inDegree = new int[numCourses];
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
    for (int[] pre : prerequisites) {
        adj.get(pre[1]).add(pre[0]);
        inDegree[pre[0]]++;
    }
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++)
        if (inDegree[i] == 0) queue.offer(i);
    int processed = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        processed++;
        for (int next : adj.get(course)) {
            if (--inDegree[next] == 0) queue.offer(next);
        }
    }
    return processed == numCourses;
}

Java

Time: O(V+E) · Space: O(V+E)