207. Course Schedule 🔥
Medium
Problem:
There are n courses represented by pairs like [0, 1], indicating that to complete course 0, one must finish course 1 first. Given the number of courses, n, and these pairs, determine if it's possible to complete all courses.
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.https://leetcode.com/problems/course-schedule/
What to learn:
RuntimeError: dictionary changed size during iteration
When iterating over defaultdict, you will get this error. By using the defaultdict from the collections module, you can handle dictionaries without keys to prevent NULL errors when accessing empty values. This means it's structured to always create a default value to avoid errors. Therefore, you need to wrap it with list() to resolve this issue. In other words, you need to create a new copy.
Solution:
Time Limit Exceeded: DFS
This problem can be solved by determining if the graph has a cyclic structure.
To identify a cyclic structure, nodes that have been previously visited are stored in the
tracedvariable.In the
dfs()function, if the current node is found in thetracedset of previously visited nodes, it indicates a cyclic structure and hence returns False. This False value will be propagated up and will eventually be the final result.Once all explorations using the current node are done, it's imperative to remove this node from
tracedusingtraced.remove(i). Failing to do so might retain the node, leading to it being explored again as a previously visited path. This can mistakenly be interpreted as a cycle.
To better understand, refer to this drawings below:
Having empty list means no prerequisites, therefore, it can be compeleted. Before marking the course node as completed, we should get rid of the prerequisite.
To detect cycle in the graph, we need one more variable called visitSet.
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
preMap = collections.defaultdict(list)
for course, pre in prerequisites:
preMap[course].append(pre)
# To keep track of the nodes currently being explored
visitSet = set()
def dfs(course):
# If cycle exists, return False
if course in visitSet:
return False
visitSet.add(course)
for pre in preMap[course]:
if not dfs(pre):
return False
visitSet.remove(course)
return True
# If the graph is not all connected
# 1 -> 2, 3 -> 4
for course in list(preMap):
if not dfs(course):
return False
return TrueNote: the graph is constructed "backwards" from what one might expect. Typically, one might expect the key to be the course and the value to be the courses that follow it. However, this representation is chosen because the DFS traversal later in the code is checking for prerequisites, so it's more convenient to have the graph structured this way.
However, the problem could also be solved with the opposite representation (where the key is the prerequisite and the value is the courses that require it), but the DFS logic would need to be adjusted accordingly.
Optimization: Pruning
The previous DFS solution explores all child nodes until a cycle is found. Therefore, by improving the structure to return True unconditionally without visiting a graph node more than once, the search time can be reduced.
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = collections.defaultdict(list)
for x, y in prerequisites:
graph[x].append(y)
traced = set()
visited = set()
def dfs(i):
# If cycle exists, return False
if i in traced:
return False
# If already visited, return True
if i in visited:
return True
traced.add(i)
for y in graph[i]:
if not dfs(y):
return False
traced.remove(i)
visited.add(i)
return True
# If the graph is not all connected
# 1 -> 2, 3 -> 4
for x in list(graph):
if not dfs(x):
return False
return TrueSummary
The method used in the provided codes above are not directly performing a topological sort. Instead, it's using Depth First Search (DFS) to detect cycles in the graph. The goal of the function is not to produce a sorted order of courses but to determine if it's possible to take all courses (i.e., if there's no cycle in the course dependency graph).
For cycle detection using DFS, the "normal" representation (where each course maps to its prerequisites) is more straightforward. Starting from a course, the DFS explores its prerequisites, and the prerequisites of its prerequisites, and so on. If at any point during this exploration you encounter a course you're currently exploring (i.e., a course in the traced set), then there's a cycle.
In summary:
If you were doing a topological sort, you'd indeed process the nodes such that
Bcomes beforeAandCcomes beforeB.But for cycle detection using DFS, the "normal" representation where
Amaps toBandBmaps toCis more direct and intuitive.
Therefore, Why is the "normal" representation suitable for this? You start from a course, explore its prerequisites, and if you ever come back to the starting course (or any course in the current DFS path), you've detected a cycle.
Last updated