## IPSC 2008

## Solution to Problem B – Breaking in

The network can be represented as a directed graph with N nodes and M arcs. The most important
servers correspond to nodes v from which the largest number of nodes is reachable by a directed
path.

The most straightforward approach is to use, for example, the Floyd-Warshall algorithm to determine for
each node the complete list of nodes reachable from it. Then, finding the most important node(s) is a matter of
simple counting. This yields an algorithm with O(N^{3}) time complexity.

Unfortunately, this is too slow for the hard input case. A simple improvement is to replace the
Floyd-Warshall algorithm by N simple searches (be it depth-first or breadth-first ones), starting from each node
of the graph. If, instead of adjacency matrix, we store the list of directly reachable nodes in a list for each vertex,
the the resulting complexity will be O(NM). This is sufficient for our purposes, as the graphs given in the input
files are relatively sparse.