## IPSC 2004

## Solution to Problem R – Dependency Problems

This problem was probably the easiest one. One possible solution works as follows.
Consider the input as a graph with vertices corresponding to the packages and
edges corresponding to the dependencies. An edge leading from **u** to **v**
denotes that **u** depends on **v**. Each vertex is colored white or black, white
meaning the package is available. The out-degree of a vertex is the number of
edges leaving it, e.g. the number of dependencies the corresponding package has.
We may install a package iff the corresponding vertex is white and has out-degree 0.

While reading the input, we compute the out-degree and color for each vertex. Also
for each vertex **v** we store a list **D(v)** containing all vertices **u** such
that there is an edge from **u** to **v** in our graph. (E.g. a list of all
packages depending on **v**.) We will simply simulate the installation process.
If there is no white vertex with out-degree 0, we are done. Otherwise we pick any
such vertex **v**, install the corresponding package and remove **v** from the graph.
By removing **v** the out-degree of vertices in **D(v)** decreases by 1.
In this way new installable packages may arise.

We will maintain all currently installable packages in a queue. In each step we pop a package
from the queue, install it and decrease the corresponding out-degrees. If we decreased the
out-degree of a white vertex to 0, we push it into the queue. The algorithm ends when there
are no more packages in the queue.

Both time and space complexity of this algorithm are linear in the size of the given graph.
Note that an optimal algorithm would use a hash table to store the names of the packages.
However, the input files were small enough and so this approach wasn't necessary.