Course Schedule (Adjacency List & BFS)

To solve the Course Schedule problem, I first visualize the input as a directed graph where courses are nodes and prerequisite pairs define the edges. My goal is to determine if a valid topological ordering exists, which implies no cycles are present. I will start by constructing an adjacency list to store the graph structure, ensuring efficient traversal. Simultaneously, I'll maintain an in-degree array to count how many prerequisites each course has. Next, I initialize a queue with all courses that have an in-degree of zero, as these can be taken immediately. Then, I perform a Breadth-First Search using Kahn's algorithm. I dequeue a course, increment a counter for completed courses, and iterate through its neighbors. For each neighbor, I decrement their in-degree. If a neighbor's in-degree drops to zero, it means all its prerequisites are met, so I enqueue it. Finally, after the queue is empty, I check if the count of processed courses equals the total number of courses. If they match, we can finish all courses; if not, a cycle exists, making it impossible. This approach runs in O(V + E) time, which is optimal for this problem type, aligning well with Cisco's focus on scalable, efficient algorithms.