UVA - 10596 - Morning Walk

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

Keywords: Graph Theory, Eulerian Cycle, Connected Components

Problem Summary

Given:

List of intersections
List of roads between intersections

We want to:

Determine whether a round trip path that visits every road exists

Glossary

CC — Connected Components

Observation

We could model the relationship between intersections and roads as an Undirected Graph, with the intersections as the vertices and the roads as the edges. It is also possible to have multiple edges (roads) that is connected to the same edges (intersections).

It is stated that kamal “does not visit a road twice not even in his way back home”. From this statement, we can deduce that the path that kamal took is a round trip. This round trip is similar to the concept of Eulerian Cycle. Eulerian Cycle is a cycle that visits every edges exactly once and start and end at the same vertex.

Undirected Graph that contains an Eulerian Cycle must fulfill this conditions:

All vertices with non-zero degrees are part of a single CC.
All vertices has an even degrees.

We can conclude that if those conditions can be fulfilled, then it must possible for kamal to do the round trip.

Algorithm

First, we need to calculate the number of degrees on each vertices, which can be calculated by counting the number of edges on each vertices. This will let us know the degrees of each vertices.

Next, we want to use the degrees data to check whether condition #1 can be fulfilled by the graph. The CC can be retrieved by combining the vertices of each edges together using a Disjoint Set. If every non-zero degree vertices belong to the same CC, then we can conclude that condition #1 is fulfilled.

Next, we want to use the degrees data to check whether condition #2 can be fulfilled by the graph. Just check whether every degrees that we’ve collected is an even number or not.

If condition #1 and #2 is fulfilled, we can conclude that an Eulerian Cycle exists and it is possible for kamal to do the round trip.

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

Implementation

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.IntStream;

/**
 * 10596 - Morning Walk
 * Time limit: 3.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1537
 */
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();

        while (in.hasNextInt()) {
            final Input input = new Input();
            input.totalIntersections = in.nextInt();
            input.totalRoads = in.nextInt();
            input.roads = new int[input.totalRoads][];
            for (int i = 0; i < input.totalRoads; i++) {
                final int[] road = new int[2];
                road[0] = in.nextInt();
                road[1] = in.nextInt();
                input.roads[i] = road;
            }

            final Output output = process.process(input);
            if (output.isPossible) out.write("Possible\n");
            else out.write("Not Possible\n");
        }


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

class Input {
    public int totalIntersections;
    public int totalRoads;
    public int[][] roads;
}

class Output {
    public boolean isPossible;
}

class Process {
    public Output process(final Input input) {
        final Output output = new Output();

        final int maxVertex = input.totalIntersections - 1;
        final int[][] edges = input.roads;
        output.isPossible = hasEulerianCycle(maxVertex, edges);

        return output;
    }

    private boolean hasEulerianCycle(final int maxVertex, final int[][] edges) {
        return isConnectedGraph(maxVertex, edges) && hasEvenDegreesOnly(maxVertex, edges);
    }

    private boolean isConnectedGraph(final int maxVertex, final int[][] edges) {
        final DisjointSet connectedComponents = getConnectedComponents(maxVertex, edges);
        final int[] degrees = getDegrees(maxVertex, edges);
        final int[] groups = IntStream.rangeClosed(0, maxVertex)
            .filter(vertex -> degrees[vertex] > 0)
            .map(connectedComponents::find)
            .distinct()
            .toArray();
        return groups.length == 1;
    }

    private DisjointSet getConnectedComponents(final int maxVertex, final int[][] edges) {
        final DisjointSet set = new DisjointSet(maxVertex);
        for (final int[] edge : edges) set.union(edge[0], edge[1]);
        return set;
    }

    private boolean hasEvenDegreesOnly(final int maxVertex, final int[][] edges) {
        final int[] degrees = getDegrees(maxVertex, edges);
        return Arrays.stream(degrees).allMatch(degree -> degree % 2 == 0);
    }

    private int[] getDegrees(final int maxVertex, final int[][] edges) {
        final int[] degrees = new int[maxVertex + 1];
        for (final int[] edge : edges) {
            for (final int vertex : edge) {
                degrees[vertex]++;
            }
        }
        return degrees;
    }
}

final class DisjointSet {
    private final int[] parents;

    public DisjointSet(final int maxVertex) {
        parents = new int[maxVertex + 1];
        for (int vertex = 0; vertex <= maxVertex; vertex++) parents[vertex] = vertex;
    }

    public int find(final int child) {
        final int parent = parents[child];
        if (parent == child) {
            return parent;
        } else {
            final int grandparent = find(parent);
            parents[child] = grandparent;
            return grandparent;
        }
    }

    public void union(final int child1, final int child2) {
        final int parent1 = find(child1);
        final int parent2 = find(child2);
        parents[parent2] = parent1;
    }
}