Parallel Courses
Understanding the Problem
We have n courses with prerequisite relationships forming a directed graph. Each semester, we can take all courses whose prerequisites have been completed. We want the minimum number of semesters to finish everything, or -1 if a cycle makes it impossible.
This is a graph problem. The courses are nodes, and the prerequisites are directed edges. Taking "any number of courses as long as prerequisites are met" means we can take all courses with zero remaining prerequisites in a single semester. That maps to processing all nodes with in-degree 0 at each step, which is what BFS-based topological sorting does, level by level.
The minimum number of semesters equals the length of the longest prerequisite chain in the graph. Courses with no prerequisites go in semester 1. Courses that depend only on semester-1 courses go in semester 2, and so on. Each BFS level corresponds to one semester. If a cycle exists, the courses on it can never be scheduled, so the answer is -1.
Key Constraints:
1 <= n <= 5000and1 <= relations.length <= 5000→ At most 5,000 nodes and 5,000 edges. The graph is sparse, so an adjacency list with O(n + E) traversal is the natural representation.prevCoursei != nextCoursei→ No self-loops, but cycles involving multiple nodes are still possible, which is why cycle detection is required to return -1.
Approach 1: BFS Topological Sort (Kahn's Algorithm)
Intuition
We can simulate the semester process directly. In each semester, we take every course whose prerequisites are already completed. In semester 1, that is the courses with no prerequisites at all, meaning their in-degree (number of incoming edges) is 0.
After finishing semester 1, we remove those courses from the graph. Some courses now have all their prerequisites satisfied, giving them in-degree 0, and those go into semester 2. We repeat until either all courses are taken or no course has in-degree 0 (a cycle means the courses on it never reach in-degree 0).
This is Kahn's algorithm for topological sorting. Instead of producing a single linear order, we process all zero-in-degree nodes together as one level (one semester) and count how many levels we need.
Taking every available course as early as possible gives the shortest schedule. A course with no remaining prerequisites can be taken now, and delaying it can only push its dependents later, never earlier, so a greedy "take it the moment it unlocks" strategy is safe.
Cycle detection comes from counting. A node on a cycle always has at least one incoming edge from another cycle member, so its in-degree never drops to 0 and it never enters the queue. When the queue empties, coursesTaken is less than n, which signals an impossible schedule.
Algorithm
- Build an adjacency list from the relations and compute the in-degree of each course.
- Add all courses with in-degree 0 to a queue. These are our semester-1 courses.
- Initialize a semester counter to 0 and a counter for courses taken.
- While the queue is not empty:
- Increment the semester counter.
- Process all courses currently in the queue (this is one semester).
- For each course, decrement the in-degree of all its neighbors. If any neighbor's in-degree becomes 0, add it to the queue.
- Add the number of courses processed to the total courses taken.
- If courses taken equals n, return the semester count. Otherwise, return -1 (cycle detected).
Visualization and Code
Loading animation...
- Time Complexity: O(n + E). Building the graph takes O(E) where E is the number of relations. The BFS visits each node once (O(n)) and processes each edge once when decrementing in-degrees (O(E)).
- Space Complexity: O(n + E). The adjacency list stores all edges (O(E)), the in-degree array uses O(n), and the queue holds at most n nodes.
The next approach reaches the same answer from a different angle. Instead of simulating semesters one level at a time, it computes the longest prerequisite chain in the graph directly with DFS.
Approach 2: DFS with Longest Path
Intuition
The minimum number of semesters equals the longest chain of prerequisites. If course A requires B, which requires C, which requires D, that is a chain of length 4, so we need at least 4 semesters no matter what else is in the graph.
The problem reduces to finding the longest path in a directed graph. For each node, we compute the longest path starting from it, and the answer is the maximum over all nodes.
DFS with memoization computes this efficiently. The longest path from a course is 1 (the course itself) plus the maximum longest path among the courses it is a prerequisite for. Caching each result avoids recomputing shared sub-chains.
Cycle detection rides along on the same traversal. If DFS reaches a node that is still being explored on the current path, the graph has a cycle. A three-state marking handles this: unvisited (0), visiting (on the DFS stack, marked -1), and visited (fully processed, a positive depth value).
Each edge is a "must come before" constraint. A chain of k courses where each depends on the previous one forces at least k semesters, since no two courses on the chain can share a semester. That makes the longest chain a lower bound. It is also achievable: scheduling every course in the semester equal to its longest incoming chain length never violates a constraint, because a dependency always sits on a shorter chain than its dependent. So the longest path is both necessary and sufficient.
Memoization keeps each node O(1) on repeat visits: once maxDepth[node] holds a positive value, later calls return it without re-exploring. Cycle detection reuses the same field. A node marked -1 is still on the active DFS stack, so reaching it again means an edge points back into the current path, which is a cycle.
Algorithm
- Build an adjacency list from the relations.
- Create an array
maxDepthto store the longest path from each node (initialized to 0, meaning unvisited). - For each course from 1 to n, if it hasn't been visited, run DFS on it.
- In the DFS function:
- Mark the node as "visiting" (set maxDepth to -1 as a sentinel).
- For each neighbor, if it's "visiting" (maxDepth == -1), we found a cycle, return -1. If it's unvisited, recurse.
- The node's depth is 1 + max depth among all neighbors (or 1 if no neighbors).
- Mark the node as "visited" by storing its computed depth.
- Return the maximum value in maxDepth. If any DFS returned -1, the whole answer is -1.
Visualization and Code
Loading animation...
- Time Complexity: O(n + E). Each node is visited exactly once due to memoization. Each edge is traversed once during DFS. Building the graph takes O(E).
- Space Complexity: O(n + E). The adjacency list stores all edges (O(E)), the maxDepth array uses O(n), and the recursion stack can go up to O(n) deep in the worst case.