Course Schedule
You are given numCourses and a list of prerequisites, where each element in prerequisites[i] = [a_i, b_i] means you must complete course b_i before taking course a_i. Write a function canFinish that returns True if it's possible to finish all courses, and False if it's not. You need to complete all the courses for the result to be True.
Assume there are no duplicate prerequisites, and numCourses is a non-negative number.
Examples
Input: numCourses = 3, prerequisites = [[2, 1], [1, 0]] Output: True Explanation: You can complete course 0 first, then course 1, and finally course 2. Input: numCourses = 4, prerequisites = [[3, 2], [2, 1], [1, 0], [0, 3]] Output: False Explanation: The prerequisites form a cycle, making it impossible to finish all courses. Input: numCourses = 5, prerequisites = [[4, 2], [3, 1], [2, 0]] Output: True Explanation: You can complete the courses in order from course 0 to course 4.
Try modeling the courses as a graph, with edges representing prerequisites. Consider how you can detect cycles to determine if all courses can be completed.
Our solution processes the input data to determine if it's possible to finish all courses given the prerequisite constraints. It constructs a directed graph where nodes represent courses and edges represent the prerequisite relationships. The solution employs a queue to manage nodes with zero in-degrees (courses with no remaining prerequisites) and uses a list to keep track of the number of prerequisites (in-degrees) for each course.
For each course with zero in-degrees, the solution dequeues it and processes its neighbors, reducing their in-degrees. If a neighbor's in-degree becomes zero, it is added to the queue. This approach ensures that all courses with no remaining prerequisites are processed and their dependencies are updated accordingly.
By maintaining a count of the number of processed courses, the solution can determine if all courses can be finished. If the count of processed courses matches the total number of courses, it implies that there are no cyclic dependencies, and thus all courses can be completed.
The solution uses a queue to efficiently manage courses with zero in-degrees and a vector to keep track of in-degrees. This method ensures that each course is processed only once, making the approach both clear and efficient.
We are using a BFS (implemented by a queue) for this solution because it helps process nodes level by level (course by course), ensuring that we first handle courses with no dependencies before moving to those that rely on other courses. This approach ensures that we can detect cycles in the course prerequisites, which would make it impossible to complete all courses.
from collections import deque, defaultdict
from typing import List
def can_finish(num_courses: int, prerequisites: List[List[int]]) -> bool:
# Create an adjacency list and an in-degree count
adj_list = defaultdict(list)
in_degree = [0] * num_courses
# Build the graph
for dest, src in prerequisites:
adj_list[src].append(dest)
in_degree[dest] += 1
# Initialize a queue with all courses having zero in-degree
queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
visited_courses = 0
# Process nodes with zero in-degree
while queue:
node = queue.popleft()
visited_courses += 1
for neighbor in adj_list[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
# Check if we visited all courses
return visited_courses == num_coursesTime Complexity: The solution has a time complexity of O(numCourses + numPrerequisites). This is because we process each course (vertex) and each prerequisite pair (edge) exactly once. The time complexity reflects the total number of courses (numCourses) and the number of prerequisite relationships (numPrerequisites).
Space Complexity: The solution uses O(numCourses + numPrerequisites) space for the adjacency list and the in-degree vector. The space complexity accounts for the storage needed for both the graph representation and the queue, which in the worst case, contains all courses.
DFS with check of an already seen node in the graph would work
from collections import deque, defaultdict from typing import List def is_course_loop_dfs(id_course: int, graph: defaultdict[list]) -> bool: stack = deque([(id_course)]) seen_courses = set() while stack: # print(stack) curr_course = stack.pop() if curr_course in seen_courses: return True seen_courses.add(curr_course) for dependency in graph[curr_course]: stack.append(dependency) return False def can_finish(num_courses: int, prerequisites: List[List[int]]) -> bool: graph = defaultdict(list) for requisite in prerequisites: course = requisite[0] dependency = requisite[1] graph[course].append(dependency) # print(graph) for id_course in range(num_courses): if is_course_loop_dfs(id_course, graph): return False return True # debug your code below print(can_finish(4, [[1, 0], [2, 1], [3, 2]]))