[link](https://leetcode.com/problems/course-schedule-ii/)
---
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.
#### Example 1:
```
Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].
```
Example 2:
```
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].
```
Example 3:
```
Input: numCourses = 1, prerequisites = []
Output: [0]
```
#### Constraints:
- 1 <= numCourses <= 2000
- 0 <= prerequisites.length <= numCourses * (numCourses - 1)
- prerequisites[i].length == 2
- 0 <= ai, bi < numCourses
- ai != bi
- All the pairs [ai, bi] are distinct.
---
An adjacency dictionary adj is initialized to represent the prerequisites for each course. It's structured such that the keys are course numbers and the values are lists of courses that depend on the key course.
Two sets, visit and cycle, are initialized to keep track of visited courses and courses involved in a cycle, respectively. An empty list res is created to store the final order of courses.
A recursive depth-first search (DFS) function dfs(pre) is defined to traverse the course prerequisites and detect cycles. Here's how the function works:
If the course pre is already in the cycle set, it means a cycle is detected, so the function returns False. If the course pre is in the visit set, it's already been explored and there's no cycle, so the function returns True. Otherwise, the course pre is added to the cycle set to mark the current path.
The function recursively traverses each dependent course crs of the current course pre. If a cycle is detected in the dependent course, the function returns False. After traversing all dependent courses, the current course is removed from the cycle set as the path is complete.
The course pre is added to the visit set, appended to the res list, and the function returns True.
The code iterates through all course numbers using a for loop and attempts to run the DFS function on each course. If a cycle is detected during the DFS, it means there's a dependency loop, and the method returns an empty list, indicating that it's not possible to complete the courses in a valid order.
If no cycles are detected, the res list is reversed to get the correct order of courses to take. The method then returns this ordered list of courses.
#### Solution 1
```python=
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
adj = { i: [] for i in range(numCourses) }
for crs, pre in prerequisites:
adj[pre].append(crs)
visit, cycle = set(), set()
res = []
def dfs(pre):
if pre in cycle:
return False
if pre in visit:
return True
cycle.add(pre)
for crs in adj[pre]:
if dfs(crs) == False:
return False
cycle.remove(pre)
visit.add(pre)
res.append(pre)
return True
for pre in range(numCourses):
if not dfs(pre):
return []
res.reverse()
return res
```
O(T): O(V + E)
O(S): O(V)
---
The adj dictionary is used to represent the adjacency list of the courses. For each course i, adj[i] stores the list of courses that are prerequisites for course i.
The visit set keeps track of the courses that have been visited during the DFS traversal. The cycle set is used to detect cycles during the DFS traversal. If a course is encountered that is already in the cycle set, it means there is a cycle in the graph. The res list will store the final order of courses.
The dfs function performs a depth-first search traversal starting from a given course crs. It returns True if a valid order can be found starting from crs and False if a cycle is detected or if it's not possible to find a valid order.
Inside the dfs function:
If the current course crs is in the cycle set, a cycle is detected, and the function returns False.
If the current course crs is in the visit set, it means this course and its prerequisites have already been explored, so the function returns True.
Otherwise, the current course is added to the cycle set to mark the current path, and the function proceeds to explore its prerequisites using a loop. If any of the prerequisites return False during the DFS traversal, indicating an invalid order, the function returns False.
If the prerequisites are explored without any issues, the current course is removed from the cycle set, added to the visit set, and appended to the res list.
Finally, the function returns True.
The outer loop iterates through all the courses (numCourses) and calls the dfs function for each course. If the dfs function returns False, indicating an invalid order, an empty list is returned. Otherwise, the res list contains the valid order of courses.
#### Solution 2
```python=
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
adj = { i: [] for i in range(numCourses) }
for crs, pre in prerequisites:
adj[crs].append(pre)
visit, cycle = set(), set()
res = []
def dfs(crs):
if crs in cycle:
return False
if crs in visit:
return True
cycle.add(crs)
for pre in adj[crs]:
if not dfs(pre):
return False
cycle.remove(crs)
visit.add(crs)
res.append(crs)
return True
for crs in range(numCourses):
if not dfs(crs):
return []
return res
```
O(T): O(V + E)
O(S): O(V)
Sign in with Wallet
Connect another wallet