Internet Problem Solving Contest

IPSC 2008

Solution to Problem R – Railroad Map

The input for this problem is a weighted graph. There were two quite obvious approaches that could be used for this problem.

One possible solution is to implement the procedure directly, each time we find a vertex of degree 2, remove it along with its both edges, and add a new edge instead. To implement this solution efficiently, we need a data structure that can store a dynamic graph that can have duplicate edges. (There are no such edges in the input, but they can be created during this process.) A simple (but not optimal) data structure is a multiset containing all edges.

The other solution is to use depth-first search (DFS). Start in a vertex that does not have degree 2. Now, each time the DFS enters a vertex with degree 2, we know that it will travel the entire path of such vertices. Each time the DFS enters a vertex that has a degree other than 2, we can output the edge of the new graph we just traversed.

To avoid special cases (two large vertices connected by an edge), it is best to preprocess the input graph – add a new vertex in the middle of each edge.