UVA - 12379 - Central Post Office

This article will explain my thought process to solve a problem called Central Post Office (PDF) from UVA Online Judge. Read the original problem statement before reading this article.

Keywords: Graph, Minimum Spanning Tree, Single-source Shortest Paths

Objective

Given:

List of cities.
List of adjacent cities.
Travel time between adjacent cities (1 hours).
Unique sequence of roads between cities.

We want to:

Find the minimum travel time to visit every cities.

Glossary

Graph — A structure consisting of a set of objects where some pairs of the objects are related.
Minimum Spanning Tree (MST) — A set of edges such that any vertex can reach any other by exactly one simple path.
Single-source Shortest Paths (SSSP) — A problem of finding the shortest paths from a single source vertex to all other vertices in a graph.
Breadth-first Search (BFS) — A graph traversal algorithm that starts from a source vertex and explores the graph level by level.

Observation

We could model the relationship between cities and roads as a graph, where the cities are the vertices and the roads are the edges. Pay attention to the “unique sequence of roads” constraint, it means that there is exactly 1 path between any vertices, hence the graph can be classified as a MST.

To visit every vertices, we may need to use some edges twice for visiting the destination vertex and returning to the origin vertex, as seen on the path between 3-5 and 1-2 above. However, there is also an edges where we only need to visit once, as seen on the path between 3-1-4 above. To minimize the travel time, we want to maximize the length of the visit once edges.

We could rephrase the problem of “maximizing the length of the visit once edges” into “finding the farthest path on a MST”. It can be done using 2-phase SSSP to find the head and tail of the farthest path.

After the farthest path is discovered, the minimum travel time to visit every vertices is equals to the {total edges} * 2 - {total edges on the farthest path}.

Algorithm

To implement the 2-phase SSSP for finding the farthest path on a MST, we could use BFS algorithm to traverse the MST. Since BFS traverse the graph vertex by vertex, the last vertex visited by the BFS automatically becomes the farthest destination vertex from the origin vertex. The first BFS phase is used to find the head of the farthest path by traversing the MST from any arbitrary vertex, and the second BFS phase is used to find the tail of the farthest path by traversing the MST from the head of the farthest path.

After the head and tail of the farthest path is discovered, we could get the total edges by counting the distance of the farthest path. As for the total edges of the MST, it is equals to the number of vertices minus one. Once the total edges is known, we can calculate the travel time using the formula of {total edges} * 2 - {total edges on the farthest path}.

The time complexity of this solution is O({total cities} + {total roads}) or O(10^4).

Implementation

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

/**
 * 12379 - Central Post Office
 * Time limit: 3.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3801
 */
public class Main {
    public static void main(final String... args) {
        final Scanner in = new Scanner(new BufferedInputStream(System.in));
        final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        final Process process = new Process();

        final int totalCases = in.nextInt();
        for (int i = 0; i < totalCases; i++) {
            final Input input = new Input();
            input.totalCities = in.nextInt();
            input.adjacentCities = new int[input.totalCities + 1][];
            for (int city = 1; city <= input.totalCities; city++) {
                final int totalAdjacentCities = in.nextInt();
                input.adjacentCities[city] = new int[totalAdjacentCities];
                for (int j = 0; j < totalAdjacentCities; j++) {
                    input.adjacentCities[city][j] = in.nextInt();
                }
            }

            final Output output = process.process(input);
            out.println(output.dispatchingTime);
        }

        in.close();
        out.flush();
        out.close();
    }
}

class Input {
    public int totalCities;
    public int[][] adjacentCities;
}

class Output {
    public int dispatchingTime;
}

class Process {
    public Output process(final Input input) {
        final UndirectedGraph<Integer> graph = createGraph(input.totalCities, input.adjacentCities);
        final Path farthestPath = findFarthestPathInMST(graph);
        final int dispatchingTime = findDispatchingTime(input.totalCities, farthestPath);

        final Output output = new Output();
        output.dispatchingTime = dispatchingTime;
        return output;
    }

    private UndirectedGraph<Integer> createGraph(final int totalCities, final int[][] adjacentCities) {
        final UndirectedGraph<Integer> graph = new UndirectedGraph<>();
        for (int city = 1; city <= totalCities; city++) {
            for (int adjacentCity : adjacentCities[city]) {
                graph.add(city, adjacentCity);
            }
        }
        return graph;
    }

    private Path findFarthestPathInMST(final UndirectedGraph<Integer> graph) {
        final Path farthestPath1 = findFarthestPath(graph, 1);
        final Path farthestPath2 = findFarthestPath(graph, farthestPath1.vertex);

        return farthestPath2;
    }

    private Path findFarthestPath(final UndirectedGraph<Integer> graph, final int originVertex) {
        final Queue<Path> pathq = new LinkedList<>();
        final Set<Integer> visited = new HashSet<>();

        final Path initial = new Path(originVertex);
        pathq.add(initial);
        visited.add(initial.vertex);

        Path last = initial;

        while (!pathq.isEmpty()) {
            final Path current = pathq.remove();
            last = current;

            for (final int nextVertex : graph.get(current.vertex)) {
                if (!visited.contains(nextVertex)) {
                    final Path next = current.next(nextVertex);
                    pathq.add(next);
                    visited.add(next.vertex);
                }
            }
        }

        return last;
    }

    private int findDispatchingTime(final int totalVertices, final Path farthestPath) {
        final int totalEdges = totalVertices - 1;
        final int totalFarthestEdges = farthestPath.distance;
        return totalEdges * 2 - totalFarthestEdges;
    }
}

final class UndirectedGraph<V> {
    public final Map<V, Set<V>> edges = new HashMap<>();

    public void add(final V vertex1, final V vertex2) {
        addDirected(vertex1, vertex2);
        addDirected(vertex2, vertex1);
    }

    private void addDirected(final V fromVertex, final V intoVertex) {
        edges.computeIfAbsent(fromVertex, k -> new HashSet<>()).add(intoVertex);
    }

    public Set<V> get() {
        return edges.keySet();
    }

    public Set<V> get(final V fromVertex) {
        return edges.getOrDefault(fromVertex, Collections.emptySet());
    }
}

class Path {
    public final Path previous;
    public final int vertex;
    public final int distance;

    public Path(final int vertex) {
        this(null, vertex, 0);
    }

    private Path(final Path previous, final int vertex, final int distance) {
        this.previous = previous;
        this.vertex = vertex;
        this.distance = distance;
    }

    public Path next(final int vertex) {
        return new Path(this, vertex, distance + 1);
    }
}