#K51482. Find Startable Tasks
Find Startable Tasks
Find Startable Tasks
You are given n tasks numbered from 1 to n and a list of dependencies. Each dependency is a pair of integers (u, v) which means that task u must be completed before task v can begin.
Your goal is to determine which tasks can be started immediately. A task can be started immediately if it has no prerequisites (i.e. no other task that must be completed before it). Formally, for each task i, if the indegree (the number of tasks that should be completed before i) is 0, then task i can be started immediately.
The answer should be a list of such tasks in ascending order.
Mathematically, if we denote the number of prerequisites for task i as \( indegree(i) \), then the tasks that can be started are:
\[ \{ i \mid 1 \leq i \leq n \text{ and } indegree(i) = 0 \} \]inputFormat
The input is given via standard input (stdin). It consists of multiple lines:
- The first line contains an integer n (1 ≤ n ≤ 105), which is the number of tasks.
- The second line contains an integer m (0 ≤ m ≤ 105), the number of dependency pairs.
- The following m lines each contain two integers u and v (1 ≤ u, v ≤ n) representing a dependency that task u must be completed before task v.
outputFormat
Print a single line to standard output (stdout) with the tasks that can be started immediately in ascending order. The tasks should be separated by a single space. If there is no such task, output an empty line.
## sample6
4
1 3
2 3
4 5
5 6
1 2 4
</p>