Problems with graphs in Java

Question

I’m making a URI issue and in the lobby they ask so.

Input: The input ends in EOF. For each test case, the first line contains two positive integers C and P that represent respectively the number of cities (2 <= C <= 50) and the number of bridges (1 <= P <= 1250). P lines follow where each line contains two positive integers X and Y (indexed from 1) indicating that there is a bridge connecting cities X and Y.

How would this EOF, my doubt is only this, I do not seek answer of the question? NOTE: I am doing in java.

Answer 1

EOF means the end of the file. Since this is used in a context where you read from the standard entry, it means the end of the System.in.

First, let’s come up with a class that represents an edge:

public final class Aresta {
    private final int origem;
    private final int destino;

    public Aresta(int origem, int destino) {
        this.origem = origem;
        this.destino = destino;
    }

    public static Aresta parse(String s) {
        String[] array = s.split(" ");
        return new Aresta(
            Integer.parseInt(array[0].trim()),
            Integer.parseInt(array[1].trim()));
    }

    public int getOrigem() {
        return origem;
    }

    public int getDestino() {
        return destino;
    }

    @Override
    public String toString() {
        return origem + "->" + destino;
    }
}

You can read all the input lines like this (Java 10+):

    public static Stream<String> linhas(Scanner s) {
        Supplier<Optional<String>> sup = () -> {
            try {
                return Optional.of(s.nextLine());
            } catch (NoSuchElementException e) {
                return Optional.empty();
            }
        };
        return Stream.generate(sup).takeWhile(Optional::isPresent).map(Optional::get);
    }

This method works when creating a Stream with lines obtained by means of method nextLine() class Scanner.

However, the method nextLine() spear one NoSuchElementException when the entry is finished, which is why this exception is captured and the return placed inside a Optional.

With the method takeWhile(Predicate), we can accept the elements of Stream until the Optional empty appear, disregarding the results from that point. Since after that, all elements Optional will not be empty, we use the .map(Optional::get) to unpack the element contained in Optional. The result is a Stream<String> containing the contents of the lines read.

And then, you can get one Stream<Aresta> thus:

    public static Stream<Aresta> arestas(Scanner s) {
        return linhas(s).map(Aresta::parse);
    }

You still need to represent your problem as a whole, including the line with the numbers C and P. We can create a class for that as well:

public final class Problema {
    private final int numeroCidades;

    private final List<Aresta> arestas;

    public Problema(int numeroCidades, List<Aresta> arestas) {
        this.numeroCidades = numeroCidades;
        this.arestas = arestas;
    }

    public static Problema parse(Scanner s) {
        String primeiraLinha = s.nextLine();
        String[] partes = primeiraLinha.split(" ");
        int c = Integer.parseInt(partes[0].trim());
        List<Aresta> arestas = LerLinhas.arestas(s).collect(Collectors.toList());
        return new Problema(c, arestas);
    }

    public int getNumeroCidades() {
        return numeroCidades;
    }

    public List<Aresta> getArestas() {
        return arestas;
    }

    @Override
    public String toString() {
        return "{c=" + numeroCidades + ", p=" + arestas.size() + ", arestas=" + arestas + "}";
    }
}

To test this:

public class LerLinhas {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in, StandardCharsets.UTF_8);
        Problema p = Problema.parse(s);
        System.out.println(p);
    }

    public static Stream<Aresta> arestas(Scanner s) {
        return linhas(s).map(Aresta::parse);
    }

    public static Stream<String> linhas(Scanner s) {
        Supplier<Optional<String>> sup = () -> {
            try {
                return Optional.of(s.nextLine());
            } catch (NoSuchElementException e) {
                return Optional.empty();
            }
        };
        return Stream.generate(sup).takeWhile(Optional::isPresent).map(Optional::get);
    }
}

Testing with this input:

5 4
2 3
1 4
2 2
4 3

Here’s the way out:

{c=5, p=4, arestas=[2->3, 1->4, 2->2, 4->3]}

So, with this you already get an instance of Problema ready for you to work. This way, you can focus on the most interesting parts of the problem without worrying about the reading and interpreting part of the given input. Note that you do not have to worry about the cases where entries are poorly formed, because the URI never runs the submitted program that way.

Note that I’m not even bothered to read the value of P here. Its value can be deducted directly from the number of lines read.