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 `true`

if you can finish all courses. Otherwise, return `false`

.

**Example 1:**

Input:numCourses = 2, prerequisites = [[1,0]]Output:trueExplanation:There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

**Example 2:**

Input:numCourses = 2, prerequisites = [[1,0],[0,1]]Output:falseExplanation: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.

**Constraints:**

`1 <= numCourses <= 10^5`

`0 <= prerequisites.length <= 5000`

`prerequisites[i].length == 2`

`0 <= ai, bi < numCourses`

- All the pairs prerequisites[i] are
**unique**.

The description was taken from https://leetcode.com/problems/course-schedule/.

`#O(C+P) Time, O(C+P) Space`

**class** **Solution**:

` `**def** **canFinish**(self, numCourses: int, prerequisites: List[List[int]]) -> bool:

` prereq_map = {}`

` seen = {}`

` `**for** course **in** range(**0**, numCourses):

` prereq_map[course] = []`

` seen[course] = False`

` `

` `**for** course, prereq **in** prerequisites:

` prereq_map[course].append(prereq)`

` `

` `**def** **dfs**(course:int) -> bool:

` `**if** seen[course]:

` `**return** False

` `**if** **not** prereq_map[course]:

` `**return** True

` seen[course] = True`

` `**for** prereq **in** prereq_map[course]:

` `**if** **not** dfs(prereq):

` `**return** False

` seen[course] = False`

` prereq_map[course] = []`

` `**return** True

` `

` `**for** course **in** range(**0**, numCourses):

` `**if** **not** dfs(course):

` `**return** False

` `**return** True

To figure out if we can complete the prerequisites for each course, we will need to get the relationships between each course and each prerequisite course that needs to be taken grouped together.

Without physically creating a graph by instantiating nodes using the input matrix, we can use an adjacency list to map each prerequisite to each course.

We can then solve this problem by performing a Depth-First Search on the number of courses that are input, go through their prerequisites and check off the ones we are able to take. If there are no cycles, meaning there aren't two classes that are prerequisites of each other then we should be able to take each course.

Let's start up by creating our adjacency list,

, and our **prereq_map**

dictionary to track cycles.**seen**

` prereq_map = {}`

` seen = {}`

We will then go through the number of courses we have to initialize an empty prerequisite array within our adjacency list, and also add them to our seen dictionary with the initial value of false since we haven't seen them yet.

` `**for** course **in** range(**0**, numCourses):

` prereq_map[course] = []`

` seen[course] = False`

Next, we will go through each course and prerequisite given from the input prerequisites list and append each prerequisite to each course within our adjacency list.

` `**for** course, prereq **in** prerequisites:

` prereq_map[course].append(prereq)`

Now we will build our recursive,

function.**dfs **

It will take as arguments, a course integer and it will return a boolean value for which the prerequisites can be satisfied for the course without cycles.

` `

**def** **dfs**(course:int) -> bool:

Being a recursive function, we need to ensure the base cases aren't met before performing a DFS on the given course.

If the course has been seen in the current DFS path, then that means the course this given prerequisite is for requires the initial course to also be taken as a prerequisite. Unless we try to bribe the dean of our college, we aren't going to be able to take the given courses so we will return false.

` `**if** seen[course]:

` `**return** False

Also, if our current course has no prerequisites, then there is nothing to do a DFS on, so we can return from here also.

` `**if** **not** prereq_map[course]:

` `**return** True

If neither of these base cases is met, we will perform our DFS.

We'll breadcrumb our path by adding our current course to the seen dictionary.

` seen[course] = True`

Then, for each prerequisite mapped to the course within the adjacency list, we will see if their prerequisites can be satisfied. If at least one of them cannot be, then we should break from the loop early and return false because we would be wasting time investigating the remaining prerequisites.

` `**for** prereq **in** prereq_map[course]:

` `**if** **not** dfs(prereq):

` `**return** False

If the prerequisites for the given function call's course can be satisfied, then we will remove our breadcrumb, wipe our prerequisite array clean, and let our recursive parent call know that the DFS is good from here.

` seen[course] = False`

` prereq_map[course] = []`

` `**return** True

Now, all there is left to do is make the initial calls.

We will iterate through each course number and run a DFS on it. The reason why we can't just run a DFS on one course and assume it will recursively run on every other course is that some courses may not have prerequisites nor are they prerequisites to others. In that case, it would be disconnected from the graph and wouldn't be searched.

If all of the courses return true from each path of their DFS, all courses can be taken.

` `**for** course **in** range(**0**, numCourses):

` `**if** **not** dfs(course):

` `**return** False

` `**return** True