# 1136. Parallel Courses    ## Approach 1: DFS

• Time: $O(|V| + |E|)$, where $|V| = n$ and $|E| = |\texttt{relations}|$
• Space: $O(|V| + |E|)$, where $|V| = n$ and $|E| = |\texttt{relations}|$
  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 36 37 38 39 40 41 enum class State { kInit, kVisiting, kVisited }; class Solution { public: int minimumSemesters(int n, vector>& relations) { vector> graph(n); vector states(n); vector depth(n, 1); for (const vector& relation : relations) { const int u = relation - 1; const int v = relation - 1; graph[u].push_back(v); } for (int i = 0; i < n; ++i) if (hasCycle(graph, i, states, depth)) return -1; return *max_element(depth.begin(), depth.end()); } private: bool hasCycle(const vector>& graph, int u, vector& states, vector& depth) { if (states[u] == State::kVisiting) return true; if (states[u] == State::kVisited) return false; states[u] = State::kVisiting; for (const int v : graph[u]) { if (hasCycle(graph, v, states, depth)) return true; depth[u] = max(depth[u], 1 + depth[v]); } states[u] = State::kVisited; return false; } }; 
  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 36 37 38 39 40 41 42 enum State { kInit, kVisiting, kVisited } class Solution { public int minimumSemesters(int n, int[][] relations) { List[] graph = new List[n]; State[] states = new State[n]; int[] depth = new int[n]; Arrays.fill(depth, 1); for (int i = 0; i < n; ++i) graph[i] = new ArrayList<>(); for (int[] relation : relations) { final int u = relation - 1; final int v = relation - 1; graph[u].add(v); } for (int i = 0; i < n; ++i) if (hasCycle(graph, i, states, depth)) return -1; return Arrays.stream(depth).max().getAsInt(); } private boolean hasCycle(List[] graph, int u, State[] states, int[] depth) { if (states[u] == State.kVisiting) return true; if (states[u] == State.kVisited) return false; states[u] = State.kVisiting; for (final int v : graph[u]) { if (hasCycle(graph, v, states, depth)) return true; depth[u] = Math.max(depth[u], 1 + depth[v]); } states[u] = State.kVisited; return false; } } 
  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 36 from enum import Enum class State(Enum): kInit = 0 kVisiting = 1 kVisited = 2 class Solution: def minimumSemesters(self, n: int, relations: List[List[int]]) -> int: graph = [[] for _ in range(n)] states = [State.kInit] * n depth =  * n for u, v in relations: graph[u - 1].append(v - 1) def hasCycle(u: int) -> bool: if states[u] == State.kVisiting: return True if states[u] == State.kVisited: return False states[u] = State.kVisiting for v in graph[u]: if hasCycle(v): return True depth[u] = max(depth[u], 1 + depth[v]) states[u] = State.kVisited return False if any(hasCycle(i) for i in range(n)): return -1 return max(depth) 

## Approach 2: Topology

• Time: $O(|V| + |E|)$
• Space: $O(|V| + |E|)$
  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 36 class Solution { public: int minimumSemesters(int n, vector>& relations) { int ans = 0; vector> graph(n); vector inDegree(n); queue q; // Build graph. for (const vector& relation : relations) { const int u = relation - 1; const int v = relation - 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()) { for (int sz = q.size(); sz > 0; --sz) { const int u = q.front(); q.pop(); --n; for (const int v : graph[u]) if (--inDegree[v] == 0) q.push(v); } ++ans; } return n == 0 ? ans : -1; } }; 
  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 36 37 class Solution { public int minimumSemesters(int n, int[][] relations) { int ans = 0; List[] graph = new List[n]; int[] inDegree = new int[n]; for (int i = 0; i < n; ++i) graph[i] = new ArrayList<>(); // Build graph. for (int[] relation : relations) { final int u = relation - 1; final int v = relation - 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()) { for (int sz = q.size(); sz > 0; --sz) { final int u = q.poll(); --n; for (final int v : graph[u]) if (--inDegree[v] == 0) q.offer(v); } ++ans; } return n == 0 ? ans : -1; } } 
  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 minimumSemesters(self, n: int, relations: List[List[int]]) -> int: ans = 0 graph = [[] for _ in range(n)] inDegree =  * n # Build graph. for u, v in relations: graph[u - 1].append(v - 1) inDegree[v - 1] += 1 # Topology q = collections.deque([i for i, d in enumerate(inDegree) if d == 0]) while q: for _ in range(len(q)): u = q.popleft() n -= 1 for v in graph[u]: inDegree[v] -= 1 if inDegree[v] == 0: q.append(v) ans += 1 return ans if n == 0 else -1