Leetcode-Problems/CourseSchedule.py at main · nafizcodes/Leetcode-Problems · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        preMap = {i:[] for i in range(numCourses)}

        for crs, pre in prerequisites:
            preMap[crs].append(pre)

    #visitSet to store the visited courses
        visitSet = set()

        def dfs(crs):
            #if the course is in visitSet then meaning creating a loop, so return False
            if crs in visitSet:
                return False
            #if the course has no preq then return true
            if preMap[crs] == []:
                return True
            #if both the conditions are False, then add the course to visitset
            visitSet.add(crs)
            for i in preMap[crs]:
                if not dfs(i):  # a course cannot be taken
                    return False

            visitSet.remove(crs)

            preMap[crs] = []    #to mark the course preq as empty
            return True


        for crs in range(numCourses):
            if not dfs(crs):
                return False

        return True


#Time Complexity - O(n+p)
#Space complexity - O(n+p)