2050. Parallel Courses III - Explanation

class Solution:
    def minimumTime(self, n: int, relations: list[list[int]], time: list[int]) -> int:
        adj = defaultdict(list)
        for src, dst in relations:
            adj[src].append(dst)

        max_time = {}

        def dfs(src):
            if src in max_time:
                return max_time[src]
            res = time[src - 1]
            for nei in adj[src]:
                res = max(res, time[src - 1] + dfs(nei))
            max_time[src] = res
            return res

        for i in range(1, n + 1):
            dfs(i)

        return max(max_time.values())

class Solution:
    def minimumTime(self, n: int, relations: list[list[int]], time: list[int]) -> int:
        adj = [[] for _ in range(n)]
        for src, dst in relations:
            adj[src - 1].append(dst - 1)

        maxTime = [-1] * n
        processed = [False] * n

        for i in range(n):
            if maxTime[i] == -1:
                stack = [i]
                while stack:
                    node = stack.pop()
                    if processed[node]:
                        best = 0
                        for nei in adj[node]:
                            best = max(best, maxTime[nei])
                        maxTime[node] = time[node] + best
                    else:
                        processed[node] = True
                        stack.append(node)
                        for nei in adj[node]:
                            if maxTime[nei] == -1:
                                stack.append(nei)
        return max(maxTime)

class Solution:
    def minimumTime(self, n: int, relations: list[list[int]], time: list[int]) -> int:
        adj = [[] for _ in range(n)]
        indegree = [0] * n
        maxTime = time[:]

        for src, dst in relations:
            adj[src - 1].append(dst - 1)
            indegree[dst - 1] += 1

        queue = deque([i for i in range(n) if indegree[i] == 0])
        while queue:
            node = queue.popleft()
            for nei in adj[node]:
                maxTime[nei] = max(maxTime[nei], maxTime[node] + time[nei])
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)

        return max(maxTime)