#C9496. Task Scheduling and Topological Order

    ID: 53595 Type: Default 1000ms 256MiB

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 and m, where n is the number of tasks and m is the number of prerequisite relations.
  • The next m lines each contain two integers a and b, indicating that task b must be completed before task a 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.

## sample
4 3
1 0
2 1
3 2
0 1 2 3