I am working on the
There are a total of n courses you have to take, labeled from
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair:
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
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.
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.
- The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
- 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
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?