Untitled

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        if not prerequisites: 
            return True
        
        # build dict of prerequisites
        graph = {i: [] for i in range(numCourses)}
        for c, p in prerequisites:
            graph[p].append(c)

        # track state of each course
        # 0 not visited
        # 1 visiting
        # 2 visited
        visited = [0] * numCourses


        def dfs(course: int) -> bool:
            if visited[course] == 1:
                return True # found a cycle
            elif visited[course] == 2:
                return False # path from here has been proven to not have a cycle
            elif graph[course] == []:
                visited[course] = 2 # leaf node, mark as visited
                return False
            visited[course] = 1 # mark this node as visiting then visit all children
            for prereq in graph[course]:
                if dfs(prereq):
                    return True
            visited[course] = 2 # if no cycle after visiting all children, mark as visited
            return False

        # iterate through each course that hasn't been visited
        for i in range(numCourses):
            if visited[i] == 0:
                if dfs(i):
                    return False
            
        return True