Problem
There arenumCourses courses labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a, b] means you must complete course b before taking course a.
Return
true if it is possible to finish all courses. Otherwise, return false. The courses cannot be completed if the prerequisite relationships contain a cycle.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
numCourses = 4
prerequisites = [[1,0],[2,1],[3,2]] Graph
0 → 1 → 2 → 3
Output
trueInput
numCourses = 3
prerequisites = [[1,0],[2,1],[0,2]]Graph
0 → 1 → 2
↑ |
└───────┘
Output
falseSolution
This solution uses Breadth-First Search (BFS) with topological sorting using Kahn's Algorithm.We first calculate the in-degree of every course. The in-degree represents how many prerequisites must be completed before that course can be taken.
All courses with an in-degree of
0 have no remaining prerequisites, so they are added to a queue. We repeatedly take a course from the queue and reduce the in-degree of the courses that depend on it.
If we are able to process all courses, there is no cycle and all courses can be completed. If some courses remain unprocessed, their dependencies form a cycle.
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
int[] inDegree = new int[numCourses];
// Create the adjacency list.
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
// Build the graph and calculate in-degrees.
for (int[] prerequisite : prerequisites) {
int course = prerequisite[0];
int requiredCourse = prerequisite[1];
graph.get(requiredCourse).add(course);
inDegree[course]++;
}
Queue<Integer> queue = new LinkedList<>();
// Add courses with no prerequisites.
for (int course = 0; course < numCourses; course++) {
if (inDegree[course] == 0) {
queue.offer(course);
}
}
int completedCourses = 0;
while (!queue.isEmpty()) {
int course = queue.poll();
completedCourses++;
// Remove this course as a prerequisite.
for (int nextCourse : graph.get(course)) {
inDegree[nextCourse]--;
if (inDegree[nextCourse] == 0) {
queue.offer(nextCourse);
}
}
}
return completedCourses == numCourses;
}
Complexity
Each course is added to the queue at most once, and each prerequisite relationship is processed once, resulting inO(V + E) time complexity.
The adjacency list, in-degree array, and queue require
O(V + E) extra space.
DFS Approach
The same problem can also be solved using Depth-First Search (DFS) to detect whether the course dependency graph contains a cycle.First, an adjacency list is created where each course points to its prerequisites. We then perform DFS starting from every course.
During DFS, a visiting array tracks courses currently being processed in the current DFS path. If we reach a course that is already being visited, a cycle exists, which means the courses cannot all be completed.
After processing all prerequisites of a course, it is marked as visited and removed from the current DFS path. If no cycle is found, all courses can be completed.
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = new ArrayList<>();
// Create the adjacency list.
for (int i = 0; i < numCourses; i++) {
graph.add(new ArrayList<>());
}
// Add prerequisite relationships.
for (int[] prerequisite : prerequisites) {
graph.get(prerequisite[0]).add(prerequisite[1]);
}
boolean[] visited = new boolean[numCourses];
boolean[] visiting = new boolean[numCourses];
for (int course = 0; course < numCourses; course++) {
if (hasCycle(course, graph, visited, visiting)) {
return false;
}
}
return true;
}
private boolean hasCycle(int course, List<List<Integer>> graph,
boolean[] visited, boolean[] visiting) {
// Found a cycle.
if (visiting[course]) {
return true;
}
// Already processed.
if (visited[course]) {
return false;
}
visiting[course] = true;
for (int prerequisite : graph.get(course)) {
if (hasCycle(prerequisite, graph, visited, visiting)) {
return true;
}
}
visiting[course] = false;
visited[course] = true;
return false;
}
Complexity
Each course and prerequisite relationship is processed at most once, resulting inO(V + E) time complexity.
The adjacency list, two visited arrays, and DFS recursion stack require
O(V + E) extra space.