A scheduler runs n tasks in synchronized rounds. A directed edge u v means u must finish before v can start. Each task takes exactly one round, and there are unlimited workers, so a task runs in the earliest round in which all its prerequisites are already finished. Round 1 runs all tasks with no prerequisites, round 2 runs all tasks whose prerequisites all finished by round 1, and so on. Output the number of tasks completed in each round, in round order.
Line 1: two integers n and m — the number of nodes (labeled 0 through n-1) and the number of directed edges.
Each of the next m lines: two integers u v, a directed edge from u to v (read as: u must come before v).
It is guaranteed the graph is acyclic, with no self-loops and no duplicate edges.
One line with the batch sizes: for round 1, round 2, ..., up to the last non-empty round, space-separated.
Example 1
Input
4 3 0 1 1 2 0 2
Expected
2 1 1
Explanation
Round 1 runs 0 and 3 (2 tasks). Round 2 runs 1 (1 task). Round 3 runs 2 (1 task). Batch sizes: 2 1 1.
Example 2
Input
3 0
Expected
3
Explanation
All three tasks are independent, so they all finish in the single first round: 3.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →