Loading...
Loading...
Loading...
A project has n tasks numbered 1 to n and m rules. A rule "a b" means task a must come before task b. Among all orders that obey every rule, print the one that is smallest when compared from the first position (at every step, the smallest available task number is used). If no order exists, print -1.
Example 1
Input
4 3 3 1 3 2 2 4
Output
3 1 2 4
Task 3 is the only start; then 1 and 2 are ready, so 1 comes first.
Example 2
Input
2 2 1 2 2 1
Output
-1
Try the problem first. Open one hint at a time.
Use Kahn's algorithm, but keep the ready tasks in a min-heap instead of a queue.
If fewer than n tasks come out, print -1.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor