UVa 10305

From Algorithmist
Jump to: navigation, search

10305 - Ordering Tasks[edit]

Summary[edit]

This is a straight forward no frills topological sort problem.

Explanation[edit]

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.

Gotcha's[edit]

  • m may be 0.

Notes[edit]

There is a special judge for this problem, any valid topological sort is accepted.

Implementations[edit]

Input[edit]

5 4
1 2
2 3
1 3
1 5
5 4
1 2
2 3
1 3
1 5
5 0
0 0

Output[edit]

4 1 5 2 3
4 1 5 2 3
5 4 3 2 1