Course Schedule II
Topological Sort DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Task Scheduling with Prerequisites (Course Schedule / Prerequisite Tasks), Graph, Directed Graph, Directed Acyclic Graph, Topological Sorting, Breadth-First Search, Cycle Detection, Adjacency List, Time Complexity, Space Complexity, Queue, Arrays, graph representation, topological sort, kahn's algorithm, graph algorithms, queue, graph properties, cycle detection, bfs, Cycle Detection in Directed Graphs, Topological Sort (Kahn's Algorithm).
Task Scheduling Order There are a total of n tasks you have to pick, labeled from 0 to n 1. Some tasks may have prerequisites; for example, to pick task 0 you have to first finish task 1, which is expressed as a pair: [0, 1]. This means task 0 depends on task 1. Given the total number of n tasks and a list of m prerequisite pairs, find one valid order of tasks you should pick to finish all tasks. If it is impossible to finish all tasks due to cyclic dependencies, return an empty array. Input Specification The first line contains an integer n, representing the total number of tasks. The second line contains an integer m, representing the number of prerequisite pairs. The next m lines each contain two integers, dependent task and prerequisite task, representing a pair [dependent task, prerequisite task] where dependent task requires prerequisite task to be completed first. Output Specification Return a list of integers representing one valid order of tasks to complete all tasks. If it is impossible to complete all tasks, return an empty array. Constraints (Constraints are not provided in the original content. Assume standard competitive programming constraints for N and M that allow for O(N+M) solutions.) Sample Test Cases Example 1: Example 2: