#C9496. Task Scheduling and Topological Order
Task Scheduling and Topological Order
Task Scheduling and Topological Order
You are given a set of tasks labeled from 0 to n-1 and a list of prerequisite pairs. Each prerequisite pair (a, b) means that task b must be completed before task a can be started. Formally, if there is a directed edge from b to a, then task b must come before task a in a valid ordering.
Your goal is to determine a valid order in which all tasks can be completed. If there are multiple valid orders, output the one obtained by a standard breadth-first topological sort (i.e. using a queue and starting with the smallest indexed tasks when possible). If no valid ordering exists (i.e. the graph contains a cycle), output -1.
In terms of formulas, if there is an edge from \( b \) to \( a \), then \( b \) must appear before \( a \) in the ordering.
inputFormat
The input is given via standard input (stdin) and consists of:
- The first line contains two integers
n
andm
, wheren
is the number of tasks andm
is the number of prerequisite relations. - The next
m
lines each contain two integersa
andb
, indicating that taskb
must be completed before taska
can be started.
outputFormat
Output a valid topological ordering of the tasks as a single line of space-separated integers. If it is impossible to complete all tasks (due to a cycle), output -1.
## sample4 3
1 0
2 1
3 2
0 1 2 3