UVA - 11770 - Lighting Away

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

Keywords: Graph, Strongly Connected Components

Objective

Given:

List of lights.
List of chain reactions between lights.

We want to:

Find the minimum number of lights that needs to be manually turned on.

Glossary

Graph — A structure consisting of a set of objects where some pairs of the objects are related.
Strongly Connected Components (SCC) — A subset of vertices where every vertex in the subset is reachable from every other vertex in the same subset by traversing the directed edges.
Kosaraju Algorithm — An algorithm attributed to S. Rao Kosaraju to find the strongly connected components in a directed graph.
Depth-first Search (DFS) — A graph traversal algorithm that starts from a source vertex and explores each path completely before backtracking and exploring other paths.

Observation

We could model the relationship between lights and its chain reactions as a graph, where the lights are the vertices and the chain reactions are the edges. The chain reactions explain which light will be turned on when a certain light is turned on, so it means that there is direction on the edges and the graph can be classified as a directed graph.

When a light is turned on, it will trigger a chain reactions that turned on several other lights as well. We can model the the chain reactions as a single source graph traversal. Our goal is to find a multi sources graph traversal that can visit the entire graph vertices with the minimum number of source vertices.

First, we need to condense the graph by grouping the vertices in the same SCC together. Every vertices in a SCC can reach is other, that is why they can be grouped together, as visiting any of the vertex means visiting the whole SCC vertices.

Next, after we have discovered the SCC graph, any SCC vertex with zero in degrees must be turned on manually, otherwise it can be turned on using the chain reactions.

Algorithm

We can implement the algorithm to find SCC in a directed graph using Kosaraju Algorithm. This is done by (1) creating 2 version of graph (normal and transposed), and (2) doing a 2-phase DFS on both graph. By taking advantage of the DFS traversal sequence, Kosaraju is able to retrieve every possible SCC in a graph.

To calculate the in degrees of each vertex in a graph, we can iterate the edges of the directed graph, and increment the count of the destination vertex.

The time complexity of this solution is O({total lights} + {total chain reactions}) or O(10^5).

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.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.Scanner;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * 11770 - Lighting Away
 * Time limit: 3.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2870
 */
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.caseId = i + 1;
            input.totalLights = in.nextInt();
            input.totalReactions = in.nextInt();
            input.reactions = new int[input.totalReactions][2];
            for (int j = 0; j < input.totalReactions; j++) {
                input.reactions[j][0] = in.nextInt();
                input.reactions[j][1] = in.nextInt();
            }

            final Output output = process.process(input);
            out.format("Case %d: %d\n", output.caseId, output.totalManualLights);
        }

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

class Input {
    public int caseId;
    public int totalLights;
    public int totalReactions;
    public int[][] reactions;
}

class Output {
    public int caseId;
    public int totalManualLights;
}

class Process {
    public Output process(final Input input) {
        final DirectedGraph<Integer, int[]> graph = createGraph(input);
        final List<Integer> vertices = createVertices(input);

        final KosarajuAlgorithm<Integer, int[]> kosaraju = new KosarajuAlgorithm<>(graph, vertices);
        final List<List<Integer>> stronglyConnectedComponents = kosaraju.findStronglyConnectedComponents();

        final DirectedGraph<Integer, int[]> sccGraph = createSccGraph(input, stronglyConnectedComponents);
        final List<Integer> sccVertices = createSccVertices(stronglyConnectedComponents);

        final Map<Integer, Integer> inDegrees = countInDegrees(sccGraph, sccVertices);
        final List<Integer> zeroVertices = sccVertices.stream()
            .filter(vertex -> inDegrees.getOrDefault(vertex, 0) == 0)
            .collect(Collectors.toList());

        final Output output = new Output();
        output.caseId = input.caseId;
        output.totalManualLights = zeroVertices.size();
        return output;
    }

    private DirectedGraph<Integer, int[]> createGraph(final Input input) {
        final DirectedGraph<Integer, int[]> graph = new DirectedGraph<>();
        for (final int[] reaction : input.reactions) {
            final int light1 = reaction[0], light2 = reaction[1];
            graph.add(light1, light2, reaction);
        }
        return graph;
    }

    private List<Integer> createVertices(final Input input) {
        return IntStream.rangeClosed(1, input.totalLights)
            .boxed()
            .collect(Collectors.toList());
    }

    private DirectedGraph<Integer, int[]> createSccGraph(
        final Input input,
        final List<List<Integer>> stronglyConnectedComponents
    ) {
        final int[] condensedVertices = new int[input.totalLights + 1];
        final Iterator<List<Integer>> it = stronglyConnectedComponents.iterator();
        for (int condensedVertex = 1; it.hasNext(); condensedVertex++) {
            final List<Integer> stronglyConnectedComponent = it.next();
            for (final int vertex : stronglyConnectedComponent) {
                condensedVertices[vertex] = condensedVertex;
            }
        }

        final DirectedGraph<Integer, int[]> graph = new DirectedGraph<>();
        for (final int[] reaction : input.reactions) {
            final int vertex1 = condensedVertices[reaction[0]];
            final int vertex2 = condensedVertices[reaction[1]];
            graph.add(vertex1, vertex2, reaction);
        }
        return graph;
    }

    private List<Integer> createSccVertices(
        final List<List<Integer>> stronglyConnectedComponents
    ) {
        return IntStream.rangeClosed(1, stronglyConnectedComponents.size())
            .boxed()
            .collect(Collectors.toList());
    }

    private Map<Integer, Integer> countInDegrees(
        final DirectedGraph<Integer, int[]> graph,
        final List<Integer> vertices
    ) {
        final Map<Integer, Integer> inDegrees = new HashMap<>();
        for (final int vertex : vertices) {
            for (final int nextVertex : graph.get(vertex)) {
                if (vertex == nextVertex) continue;
                inDegrees.put(nextVertex, inDegrees.getOrDefault(nextVertex, 0) + 1);
            }
        }
        return inDegrees;
    }
}

final class KosarajuAlgorithm<V, E> {
    private final DirectedGraph<V, E> graph;
    private final DirectedGraph<V, E> transposeGraph;
    private final List<V> vertices;

    public KosarajuAlgorithm(final DirectedGraph<V, E> graph, final List<V> vertices) {
        this.graph = graph;
        this.transposeGraph = transposeGraph(graph);
        this.vertices = vertices;
    }

    private DirectedGraph<V, E> transposeGraph(final DirectedGraph<V, E> graph) {
        final DirectedGraph<V, E> transpose = new DirectedGraph<>();
        for (final V fromVertex : graph.get()) {
            for (final V intoVertex : graph.get(fromVertex)) {
                final E edge = graph.get(fromVertex, intoVertex).orElseThrow(NullPointerException::new);
                transpose.add(intoVertex, fromVertex, edge);
            }
        }

        return transpose;
    }

    public List<List<V>> findStronglyConnectedComponents() {
        final Set<V> visited = new HashSet<>();
        final LinkedList<V> sequence = new LinkedList<>();

        for (final V vertex : vertices) {
            if (visited.contains(vertex)) continue;

            depthFirstSearch(graph, vertex, visited, sequence);
        }

        final List<List<V>> stronglyConnectedComponents = new LinkedList<>();
        visited.clear();
        for (final Iterator<V> it = sequence.descendingIterator(); it.hasNext(); ) {
            final V vertex = it.next();
            if (visited.contains(vertex)) continue;

            final LinkedList<V> stronglyConnectedComponent = new LinkedList<>();
            depthFirstSearch(transposeGraph, vertex, visited, stronglyConnectedComponent);
            stronglyConnectedComponents.add(stronglyConnectedComponent);
        }

        return stronglyConnectedComponents;
    }

    private void depthFirstSearch(
        final DirectedGraph<V, E> graph,
        final V vertex,
        final Set<V> visited,
        final LinkedList<V> sequence
    ) {
        if (visited.contains(vertex)) return;

        visited.add(vertex);
        for (final V nextVertex : graph.get(vertex)) {
            depthFirstSearch(graph, nextVertex, visited, sequence);
        }
        sequence.addLast(vertex);
    }
}

final class DirectedGraph<V, E> {
    private final Map<V, Map<V, E>> edges = new HashMap<>();

    public void add(final V fromVertex, final V intoVertex, final E edge) {
        edges
            .computeIfAbsent(fromVertex, k -> new HashMap<>())
            .put(intoVertex, edge);
    }

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

    public Set<V> get(final V vertex) {
        return edges
            .getOrDefault(vertex, Collections.emptyMap())
            .keySet();
    }

    public Optional<E> get(final V vertex1, final V vertex2) {
        return Optional.ofNullable(
            edges
                .getOrDefault(vertex1, Collections.emptyMap())
                .get(vertex2)
        );
    }
}