Course Schedule
- 3 min read
- Graph
- LC-Medium
3 years ago
Solution
- Visualize the problem like above.
- Make a map where key is the course and the value is the list of prerequisites for that course.
- In this problem, whether or not a course can be complete is represented by the prerequisite list being empty
- I.e. take the course 4 for example. It has no prereqs, so it can be completed.
- If you're doing a DFS starting from 0, you will reach 4, then when you're going back up the call stack, since 4 can be complete, we remove the prerequisite from the list of 3's prereqs so that we know that 3 can also be completed.
- This prerequisite removel doesn't happen one at a time because we'll be recursively calling a Depth-first Search on each of the pre-reqs to see if it's completable. If even one returns False, we return False for the algorithm. If we get through everything, we set the pre reqs of that course to an empty list.
- Okay so the above was for a list of courses that could be successfully completed. But what about an invalid case? Take the below:
- We would be using a visited set to keep track of nodes that have already been visited.
- If we visit a node that has already been visited, we know that there's a cycle in the graph, which means that the courses cannot be completed.
For future Faaez
-
Just watch the Neetcode video. You'll understand.
-
Basically, we remove the course from the visited set because we only need to maintain it for a particular graph. Take the following example:
-
Assume the 3 node in the bottom is a 4.
-
From node 1, it has two paths. Let's say it goes to 2. It'll mark it as visited. Then go to 3 (the 3 on the bottom), and so on
-
Then, it backtracks. If it doesn't remove the 2 from the visited set, it'll start a DFS from 1, visit 3, check it's pre-reqs, go to 2, and see that 2 is visited, and incorrectly mark it as a cycle.
-
This is why we do
vis.remove(crs)because there could be multiple paths starting from a single node and we don't want the results of a previous DFS interfering with the current DFS.
| Time | Space | Explanation |
|---|---|---|
O(n + p) | O() | where n is the number of nodes and p is the number of prerequisites. N is equal to vertexes and P is equal to edges i.e. O(e + v ) |
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
pre_reqs = defaultdict(list)
for crs, pre in prerequisites:
pre_reqs[crs].append(pre)
vis = set()
def dfs(crs):
if crs in vis:
return False
if pre_reqs[crs] == []:
return True
vis.add(crs)
for pre in pre_reqs[crs]:
if not dfs(pre):
return False
vis.remove(crs)
pre_reqs[crs] = []
return True
for crs in range(numCourses):
if not dfs(crs):
return False
return True