Parallel Courses

Medium · Graphs · Explanation and code example

Depth-First Search: Combine

How it works

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.

Steps

  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.

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.

Things to watch for

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.

Python code example

from typing import List

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

C++ code example

class Solution {
public:
    int minimumSemesters(int N, vector<vector<int>>& relations) {
        vector<vector<int>> graph(N + 1);
        for (auto& relation : relations) {
            graph[relation[0]].push_back(relation[1]);
        }

        vector<int> visited(N + 1, 0);
        int maxLength = 1;
        for (int node = 1; node < N + 1; node++) {
            int length = dfs(node, graph, visited);
            // we meet a cycle!
            if (length == -1) {
                return -1;
            }
            maxLength = max(length, maxLength);
        }
        return maxLength;
    }

private:
    int dfs(int node, vector<vector<int>>& graph, vector<int>& visited) {
        // return the longest path (inclusive)
        if (visited[node] != 0) {
            return visited[node];
        } else {
            // mark as visiting
            visited[node] = -1;
        }
        int maxLength = 1;
        for (auto& endNode : graph[node]) {
            int length = dfs(endNode, graph, visited);
            // we meet a cycle!
            if (length == -1) {
                return -1;
            }
            maxLength = max(length + 1, maxLength);
        }
        // mark as visited
        visited[node] = maxLength;
        return maxLength;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations