# UVa 10305

Jump to navigation
Jump to search

## Contents

## 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