UVa 10305
From Algorithmist
Contents |
[edit] 10305 - Ordering Tasks
[edit] Summary
This is a straight forward no frills topological sort problem.
[edit] Explanation
We are given a list of n tasks and a list of m dependencies between the tasks. We need to find an ordering between the tasks such that each task is executed after its dependencies have been executed. It's easy to see that if we construct a directed acyclic graph where the tasks are the vertices, and dependencies are directed edges between tasks, a topological sort will give us exactly what is needed.
[edit] Gotcha's
- m may be 0.
[edit] Notes
There is a special judge for this problem, any valid topological sort is accepted.
[edit] Input
5 4 1 2 2 3 1 3 1 5 5 4 1 2 2 3 1 3 1 5 5 0 0 0
[edit] Output
4 1 5 2 3 4 1 5 2 3 5 4 3 2 1
