# the memory usage to “CourseSchedule” algorithms

I am working on the CourseSchedule problem

Course Schedule - LeetCode

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:

Input: 2, [[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.


Example 2:

Input: 2, [[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.


Note:

1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
2. You may assume that there are no duplicate edges in the input prerequisites.

from typing import List
#from collection import deque
class Solution:
def canFinish(self, numCourses: int, prequisites: List[List[int]]) -> bool:
"""
:rtype:bool
"""
#base case
if numCourses == None or prequisites == None:  return None

#Construct a directed graph from prerequisites.
#initiate the graph, The nodes are 0 to n-1(nodes are origins)
graph = [[] for _ in range(numCourses)]
# there is an edge from i to j if i is the prerequisite of j.
for x, y in prequisites:
graph[x].append(y)
#hold the paint status
#we initiate nodes which have not been visited, paint them as 0
paint = [0 for _ in range(numCourses)]
#if node is being visiting, paint it as -1, if we find a node painted as -1 in dfs,then there is a ring
#if node has been visited, paint it as 1

def dfs(i):
#base cases
if paint[i] == -1: #a ring
return False
if paint[i] == 1: #visited
return True
paint[i] = -1 #paint it as being visiting.
for j in graph[i]: #traverse i's neighbors
if not dfs(j): #if there exist a ring.
return False