Parallel Courses III (DFS)

class Solution:
    def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int:

        def solve(n, relations, time):
            time = [0] + time
            # build reverse graph
            graph = [[] for _ in range(n+1)]
            for x, y in relations:
                graph[y].append(x)

            cache = {}
            def dfs(course):
                if course in cache:
                    return cache[course]

                max_prereq_time = 0
                for prereq in graph[course]:
                    max_prereq_time = max(max_prereq_time, dfs(prereq))

                cache[course] = max_prereq_time + time[course]
                return cache[course]

            return max(dfs(i) for i in range(1, n+1))

        return solve(n, relations, time)