Ggthjy

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.

My solution and detailed comments

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

            paint[i] = 1 #paint as visited and jump to the next.

            return True

        for i in range(numCourses):

            if not dfs(i): #if there exist a ring.

                return False

        return True

get scores

Runtime: 48 ms, faster than 87.39% of Python3 online submissions for Course Schedule.

Memory Usage: 16.2 MB, less than 11.61% of Python3 online submissions for Course Schedule.

How could improve the memory usage?