Can All the Courses Be Completed
Solve this ProblemA school offers n courses, and some courses can only be taken after others. The requirements are given as an adjacency list of a directed graph: courses[u] holds the courses that require course u first. Decide whether all courses can be completed.
This is equivalent to asking whether the graph has no cycle. Kahn's algorithm answers it by repeatedly taking courses whose requirements are all finished and checking whether every course ends up taken.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ n ≤ 8 courses numbered 0 … n-1; courses[u] lists, in increasing order, every course v that requires course u to be completed first (adjacency-list form of a directed graph) - ◆
No course is listed twice for the same u; a course may require itself (a road u → u), which can never be satisfied - ◆
You take courses one at a time - ◆
Return true if it is possible to complete all courses, otherwise false
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Look for Any Ordering That Respects Every Requirement
BruteAll courses can be completed exactly when some ordering of the courses puts every course after the courses it requires. So generate the orderings one by one, check every requirement u → v (u must appear before v), and return true as soon as one passes. If all n! orderings fail, return false. Correct, but hopeless for large n.
O(n! · (n + E))O(n)1class Solution {
2 private boolean respectsRoads(int[][] courses, int[] order) {
3 int n = courses.length;
4 int[] position = new int[n];
5 for (int i = 0; i < n; i++) position[order[i]] = i;
6 for (int u = 0; u < n; u++) {
7 for (int v : courses[u]) {
8 if (position[u] >= position[v]) return false;
9 }
10 }
11 return true;
12 }
13
14 private boolean search(int[][] courses, int[] order, int len, boolean[] used) {
15 int n = courses.length;
16 if (len == n) return respectsRoads(courses, order);
17 for (int v = 0; v < n; v++) {
18 if (used[v]) continue;
19 used[v] = true;
20 order[len] = v;
21 if (search(courses, order, len + 1, used)) return true;
22 used[v] = false;
23 }
24 return false;
25 }
26
27 public boolean canFinishAll(int[][] courses) {
28 return search(courses, new int[courses.length], 0, new boolean[courses.length]);
29 }
30}Optimal — Kahn’s Algorithm: Count the Courses You Can Take
OptimalCount for each course how many requirements are still unfinished (its indegree). Courses with indegree 0 can be taken now. Take one from the queue, count it, and cross it off: reduce the indegree of every course that requires it, and queue those that reach 0. In the end, if every course got taken, the requirements are satisfiable; if some are left, they wait on each other in a cycle. Each course and requirement is processed once: O(n + E).
O(n + E)O(n)1class Solution {
2 public boolean canFinishAll(int[][] courses) {
3 int n = courses.length;
4 int[] indegree = new int[n];
5 for (int u = 0; u < n; u++) {
6 for (int v : courses[u]) indegree[v]++;
7 }
8 Deque<Integer> queue = new ArrayDeque<>();
9 for (int i = 0; i < n; i++) {
10 if (indegree[i] == 0) queue.add(i);
11 }
12 int taken = 0;
13 while (!queue.isEmpty()) {
14 int u = queue.poll();
15 taken++;
16 for (int v : courses[u]) {
17 indegree[v]--;
18 if (indegree[v] == 0) queue.add(v);
19 }
20 }
21 return taken == n;
22 }
23}