Solution Explanation: Minimum Semesters to Complete Courses

This problem involves finding the minimum number of semesters required to complete a set of courses, given prerequisite relationships between them. The solution uses topological sorting, a graph algorithm suitable for resolving dependencies.

Approach:

1. Graph Representation: We represent the courses and their prerequisites as a directed graph. Each course is a node, and a directed edge from course A to course B indicates that B requires A as a prerequisite.

2. In-degree Calculation: For each course, we calculate its in-degree, which is the number of incoming edges (prerequisites).

3. Topological Sort: We perform topological sorting using a queue. Initially, we enqueue all courses with an in-degree of 0 (no prerequisites).

4. Iterative Processing: In each iteration, we dequeue a course. This represents completing that course in the current semester. We then decrement the in-degree of all its successors (courses that depend on it). If a successor's in-degree becomes 0, we add it to the queue, signifying that it's now ready to be taken.

5. Semester Count: Each iteration of the main loop represents a semester. We increment the semester counter (ans) in each iteration.

6. Cycle Detection: If, after processing all courses with in-degree 0, there are still courses left ( n > 0 ), it implies a cycle in the graph – a situation where courses depend on each other circularly, making it impossible to complete all courses. In this case, we return -1.

Time Complexity Analysis:

• Building the graph takes O(m) time, where m is the number of relations (edges).
• Calculating in-degrees takes O(n) time, where n is the number of courses (nodes).
• Topological sorting takes O(n + m) time in the worst case (visiting each node and edge once).
• Therefore, the overall time complexity is O(n + m).

Space Complexity Analysis:

• The graph (adjacency list) uses O(n + m) space.
• The indeg array requires O(n) space.
• The queue uses O(n) space in the worst case (all nodes in the queue).
• The overall space complexity is O(n + m).

Code Examples:

The provided code examples in Python, Java, C++, Go, and TypeScript all follow this approach. They differ slightly in syntax and data structure choices, but the core algorithm remains consistent. The use of a queue (or deque in Python) and iterative processing is key to the efficient topological sort. Note the handling of the n counter to detect cycles. If n is greater than 0 at the end, there was a cycle, and -1 is returned.

Example Walkthrough (Example 1):

n = 3, relations = [[1,3],[2,3]]

1. Graph: Course 1 -> Course 3, Course 2 -> Course 3
2. In-degrees: Course 1: 0, Course 2: 0, Course 3: 2
3. Iteration 1: Course 1 and Course 2 are enqueued (in-degree 0). They are dequeued, n becomes 1. Course 3's in-degree becomes 0, and it's enqueued. ans becomes 1.
4. Iteration 2: Course 3 is dequeued, n becomes 0. ans becomes 2.
5. Result: 2 semesters are needed.

This detailed explanation, along with the provided code examples and complexity analysis, gives a comprehensive understanding of how to solve the "Parallel Courses" problem using topological sorting.