# 2050. Parallel Courses III

• Time: $O(|V| + |E|)$, where $|V| = n$ and $|E| = |\texttt{relations}|$
• Space:
  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 class Solution { public: int minimumTime(int n, vector>& relations, vector& time) { vector> graph(n); vector inDegree(n); queue q; vector dist(time); // Build graph. for (const vector& r : relations) { const int u = r[0] - 1; const int v = r[1] - 1; graph[u].push_back(v); ++inDegree[v]; } // Topology for (int i = 0; i < n; ++i) if (inDegree[i] == 0) q.push(i); while (!q.empty()) { const int u = q.front(); q.pop(); for (const int v : graph[u]) { dist[v] = max(dist[v], dist[u] + time[v]); if (--inDegree[v] == 0) q.push(v); } } return *max_element(dist.begin(), dist.end()); } }; 
  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 class Solution { public int minimumTime(int n, int[][] relations, int[] time) { List[] graph = new List[n]; int[] inDegree = new int[n]; int[] dist = time.clone(); for (int i = 0; i < n; ++i) graph[i] = new ArrayList<>(); // Build graph. for (int[] r : relations) { final int u = r[0] - 1; final int v = r[1] - 1; graph[u].add(v); ++inDegree[v]; } // Topology Queue q = IntStream.range(0, n) .filter(i -> inDegree[i] == 0) .boxed() .collect(Collectors.toCollection(ArrayDeque::new)); while (!q.isEmpty()) { final int u = q.poll(); for (final int v : graph[u]) { dist[v] = Math.max(dist[v], dist[u] + time[v]); if (--inDegree[v] == 0) q.offer(v); } } return Arrays.stream(dist).max().getAsInt(); } } 
  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 class Solution: def minimumTime(self, n: int, relations: List[List[int]], time: List[int]) -> int: graph = [[] for _ in range(n)] inDegree = [0] * n dist = time.copy() # Build graph. for a, b in relations: u = a - 1 v = b - 1 graph[u].append(v) inDegree[v] += 1 # Topology q = collections.deque([i for i, d in enumerate(inDegree) if d == 0]) while q: u = q.popleft() for v in graph[u]: dist[v] = max(dist[v], dist[u] + time[v]) inDegree[v] -= 1 if inDegree[v] == 0: q.append(v) return max(dist)