class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:

        # DP with memoization
        # state: 0 - unvisited
        # state: 1 - visited but not finished
        # state: 2 - visited and finished
        visit = [0]*numCourses
        from collections import defaultdict
        mapping = defaultdict(list)
        for (crs, prereq) in prerequisites:
            mapping[crs].append(prereq)

        def dfs(course):
            if visit[course] == 1:
                return False

            if visit[course] == 2:
                return True

            visit[course] = 1

            for neighbour in mapping[course]:
                run = dfs(neighbour)
                if run is False:
                    return False

            visit[course] = 2
            return True

        for crs in range(numCourses):
            run = dfs(crs)
            if run is False:
                return False

        return True