mediumGraphs

Course Schedule

Courses are labeled 0 through n-1. Each pair a b means b must be completed before a. Determine whether all courses can be finished.

LeetCode ↗

Work through the cases

3 examples

Input notation

n on line 1; prerequisite pairs on subsequent lines. There may be no pairs.

Expected result

true or false.

Case 1

Input

3
1 0
2 1

Expected output

true

Case 2

Input

2
1 0
0 1

Expected output

false

Case 3

Input

Expected output

true

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Prerequisites form a directed graph; finishing every course is possible iff the graph is acyclic. Enumerating orders is not viable at the given size. Kahn's algorithm repeatedly takes a vertex of indegree 0 and decrements its successors. If every course enters the queue, there is no cycle.

For this problem, we can consider the courses as nodes in a graph, and prerequisites as edges in the graph. Thus, we can transform this problem into determining whether there is a cycle in the directed graph.

Specifically, we can use the idea of topological sorting. For each node with an in-degree of 0, we reduce the in-degree of its out-degree nodes by 1, until all nodes have been traversed.

If all nodes have been traversed, it means there is no cycle in the graph, and we can complete all courses; otherwise, we cannot complete all courses.

The time complexity is O(n + m), and the space complexity is O(n + m). Here, n and m are the number of courses and prerequisites respectively.

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] g = new List[numCourses];
        Arrays.setAll(g, k -> new ArrayList<>());
        int[] indeg = new int[numCourses];
        for (var p : prerequisites) {
            int a = p[0], b = p[1];
            g[b].add(a);
            ++indeg[a];
        }
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < numCourses; ++i) {
            if (indeg[i] == 0) {
                q.offer(i);
            }
        }
        while (!q.isEmpty()) {
            int i = q.poll();
            --numCourses;
            for (int j : g[i]) {
                if (--indeg[j] == 0) {
                    q.offer(j);
                }
            }
        }
        return numCourses == 0;
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.