1. Breadth-First Search (Kahn's Algorithm)

Intuition

This problem asks for the minimum number of semesters to complete all courses with prerequisites. Since we can take multiple courses in parallel each semester (as long as their prerequisites are met), this naturally maps to a topological sort problem where we process courses level by level.

Kahn's algorithm works perfectly here. We start with courses that have no prerequisites (in-degree of 0) and take them all in the first semester. Then we remove their outgoing edges, which may unlock new courses for the next semester. Each BFS level represents one semester.

If we cannot complete all courses (due to a cycle), we return -1.

Algorithm

1. Build an adjacency list and compute in-degrees for all courses.
2. Initialize a queue with all courses having in-degree 0 (no prerequisites).
3. Process the queue level by level, where each level represents a semester:
   • For each course in the current level, decrement the in-degree of its dependent courses.
   • Add any course whose in-degree becomes 0 to the next level.
   • Increment the semester counter.
4. If all courses are processed, return the number of semesters. Otherwise, return -1.

class Solution:
    def minimumSemesters(self, N: int, relations: List[List[int]]) -> int:
        graph = {i: [] for i in range(1, N + 1)}
        in_count = {i: 0 for i in range(1, N + 1)}  # or in-degree
        for start_node, end_node in relations:
            graph[start_node].append(end_node)
            in_count[end_node] += 1

        queue = []
        # we use list here since we are not
        # popping from the front in this code
        for node in graph:
            if in_count[node] == 0:
                queue.append(node)

        step = 0
        studied_count = 0
        # start learning with BFS
        while queue:
            # start new semester
            step += 1
            next_queue = []
            for node in queue:
                studied_count += 1
                end_nodes = graph[node]
                for end_node in end_nodes:
                    in_count[end_node] -= 1
                    # if all prerequisite courses learned
                    if in_count[end_node] == 0:
                        next_queue.append(end_node)
            queue = next_queue

        return step if studied_count == N else -1

Time & Space Complexity

• Time complexity: $O(N + E)$
• Space complexity: $O(N + E)$

Where $E$ is the length of relations and $N$ is the number of courses.

---

2. Depth-First Search: Check for Cycles + Find Longest Path

Intuition

The minimum number of semesters equals the length of the longest path in the prerequisite graph. This is because courses along the longest dependency chain must be taken sequentially, one per semester.

This approach uses two DFS passes: first to detect cycles (making it impossible to finish), then to find the longest path from any starting node. We use memoization to avoid recomputing path lengths for nodes we have already visited.

Algorithm

1. Build an adjacency list from the relations.
2. First dfs pass: detect cycles using three states (unvisited, visiting, visited).
   • If we encounter a node in the "visiting" state, a cycle exists.
   • Return -1 if any cycle is found.
3. Second dfs pass: compute the longest path starting from each node.
   • For each node, recursively find the maximum path length through its neighbors.
   • Cache results to avoid redundant computation.
4. Return the maximum path length across all nodes.

class Solution:
    def minimumSemesters(self, N: int, relations: List[List[int]]) -> int:
        graph = {i: [] for i in range(1, N + 1)}
        for start_node, end_node in relations:
            graph[start_node].append(end_node)

        # check if the graph contains a cycle
        visited = {}

        def dfs_check_cycle(node: int) -> bool:
            # return True if graph has a cycle
            if node in visited:
                return visited[node]
            else:
                # mark as visiting
                visited[node] = -1
            for end_node in graph[node]:
                if dfs_check_cycle(end_node):
                    # we meet a cycle!
                    return True
            # mark as visited
            visited[node] = False
            return False

        # if has cycle, return -1
        for node in graph.keys():
            if dfs_check_cycle(node):
                return -1

        # if no cycle, return the longest path
        visited_length = {}

        def dfs_max_path(node: int) -> int:
            # return the longest path (inclusive)
            if node in visited_length:
                return visited_length[node]
            max_length = 1
            for end_node in graph[node]:
                length = dfs_max_path(end_node)
                max_length = max(length+1, max_length)
            # store it
            visited_length[node] = max_length
            return max_length

        return max(dfs_max_path(node)for node in graph.keys())

Time & Space Complexity

• Time complexity: $O(N + E)$
• Space complexity: $O(N + E)$

Where $E$ is the length of relations and $N$ is the number of courses.

---

3. Depth-First Search: Combine

Intuition

We can combine cycle detection and longest path computation into a single DFS. The key insight is that a node in the "visiting" state during DFS indicates a cycle. We use -1 as a sentinel value to indicate both "currently visiting" and "cycle detected."

When we finish processing a node, we store its longest path length. If we ever encounter -1 from a recursive call, we propagate that cycle indicator upward. This eliminates the need for a separate cycle detection pass.

Algorithm

1. Build an adjacency list from the relations.
2. Run dfs from each unvisited node:
   • Mark the node as visiting (-1).
   • Recursively compute the longest path through neighbors.
   • If any neighbor returns -1, propagate the cycle indicator.
   • Store the computed path length and return it.
3. Track the maximum path length across all nodes.
4. Return -1 if a cycle was detected, otherwise return the maximum path length.

class Solution:
    def minimumSemesters(self, N: int, relations: List[List[int]]) -> int:
        graph = {i: [] for i in range(1, N + 1)}
        for start_node, end_node in relations:
            graph[start_node].append(end_node)

        visited = {}

        def dfs(node: int) -> int:
            # return the longest path (inclusive)
            if node in visited:
                return visited[node]
            else:
                # mark as visiting
                visited[node] = -1

            max_length = 1
            for end_node in graph[node]:
                length = dfs(end_node)
                # we meet a cycle!
                if length == -1:
                    return -1
                else:
                    max_length = max(length+1, max_length)
            # mark as visited
            visited[node] = max_length
            return max_length

        max_length = -1
        for node in graph.keys():
            length = dfs(node)
            # we meet a cycle!
            if length == -1:
                return -1
            else:
                max_length = max(length, max_length)
        return max_length

Time & Space Complexity

• Time complexity: $O(N + E)$
• Space complexity: $O(N + E)$

Where $E$ is the length of relations and $N$ is the number of courses.

---

Common Pitfalls

Forgetting to Detect Cycles

If the prerequisite graph contains a cycle, it is impossible to complete all courses. Returning the longest path length without first checking for cycles will give a wrong answer. Always verify that all courses can be processed (studied count equals N) before returning the result.

Counting Courses Instead of Semesters in BFS

With Kahn's algorithm, each BFS level represents one semester, not one course. The answer is the number of levels traversed, not the total number of courses processed. Incrementing the counter for each course instead of each level gives an incorrect result.

Using the Wrong DFS State Values

When combining cycle detection with longest path calculation, using -1 as both "visiting" and "cycle detected" requires careful handling. If a node returns -1, you must propagate this upward immediately rather than continuing to compute path lengths.