Solution Explanation: Course Schedule II

This problem asks to find a topological ordering of courses based on prerequisites. A topological ordering is a linear ordering of nodes in a directed acyclic graph (DAG) such that for every directed edge from node A to node B, node A appears before node B in the ordering. If a cycle exists (meaning it's not a DAG), a topological ordering is impossible.

This solution uses Kahn's algorithm, a topological sort algorithm based on breadth-first search (BFS).

Algorithm:

1. Build the graph: Create an adjacency list (graph) g representing the course dependencies. g[i] contains a list of courses that depend on course i. Also, create an indegree array where indegree[i] stores the number of courses that must be taken before course i.

2. Find starting nodes: Add all courses with an indegree of 0 to a queue q. These courses have no prerequisites and can be taken first.

3. BFS traversal: While the queue is not empty:

   • Dequeue a course i from the queue and add it to the ans array (the result).
   • For each course j that depends on course i (neighbors in the graph):
     • Decrement its indegree by 1.
     • If indegree[j] becomes 0, it means all its prerequisites are met, so add it to the queue.

4. Check for cycles: If the length of ans is equal to numCourses, it means all courses have been processed, and a topological ordering has been found. Otherwise, a cycle exists, and an empty array is returned.

Time Complexity Analysis:

• Building the graph: O(V + E), where V is the number of courses (vertices) and E is the number of prerequisites (edges).
• BFS traversal: O(V + E) because each vertex and edge is visited at most once.
• Therefore, the overall time complexity is O(V + E), which is linear in the size of the input graph.

Space Complexity Analysis:

• The adjacency list g requires O(V + E) space.
• The indegree array requires O(V) space.
• The queue q and the ans array require O(V) space in the worst case.
• Therefore, the overall space complexity is O(V + E).

Code Explanations (Python Example):

from collections import defaultdict, deque
 
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        g = defaultdict(list)  # Adjacency list
        indeg = [0] * numCourses  # Indegree array
        for a, b in prerequisites: #Building the graph and indegree array
            g[b].append(a)
            indeg[a] += 1
 
        q = deque(i for i, x in enumerate(indeg) if x == 0) #Finding starting nodes
 
        ans = []  # Result array
        while q: #BFS Traversal
            i = q.popleft()
            ans.append(i)
            for j in g[i]:
                indeg[j] -= 1
                if indeg[j] == 0:
                    q.append(j)
 
        return ans if len(ans) == numCourses else [] #Checking for Cycles
 

The other language examples follow the same algorithm with minor syntactic variations. They all efficiently solve the problem using Kahn's algorithm, achieving a linear time complexity.