Internet Problem Solving Contest

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(N3) 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.