Course Schedule II
- 2 min read
- Graph
- LC-Medium
3 years ago
Solution
- Do Course Schedule first
- Very similar to Course Schedule, but a slight difference is that you need to use another set
- In course schedule 1, if you visited a set that we already established as being completable, i.e. has no prerequisites, you just return True
- But here, if you visit a course that you've already established as being completable, you should only add it to the answer if it has not been added already. We achieve this using the
visitedset. If we're at a course that has already been visited (i.e. marked completable, and added to our answer already), then we just return - Everything else is about the same. In Course Schedule I if we revisited a node that was already visited, we could just return True. Here we have to add the node to the answer (if it hasn't) been added already, hence the use of another set.
- But here, if you visit a course that you've already established as being completable, you should only add it to the answer if it has not been added already. We achieve this using the
- The
visitingset is just used for Depth-first Search. It is akin to thevisset in Course Schedule - Can get confusing a little but just persevere- it is very similar to Course Schedule
| Time | Space | Explanation |
|---|---|---|
O(e + v) | O(e + v) |
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
prereqs = defaultdict(set)
for crs, pre in prerequisites:
prereqs[crs].add(pre)
order = []
visting = set()
visited = set()
def dfs(crs):
if crs in visting:
return False
if crs in visited:
return True
visting.add(crs)
for prereq in prereqs[crs]:
if not dfs(prereq):
return False
prereqs[crs] = set()
visting.remove(crs)
visited.add(crs)
order.append(crs)
return True
for crs in range(numCourses):
if not dfs(crs):
return []
return order