Problems with graphs in Java

5

I'm making a URI question and in the input they ask so.

  

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

How would this EOF be, my doubt is just that, do I look for an answer to the question? NOTE: I'm doing it in java.

    
asked by anonymous 06.09.2018 / 16:12

1 answer

1

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

First, let's create 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 lines of the input 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 by creating a Stream . with rows obtained through the method nextLine() of class Scanner .

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

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

And then, you can get a Stream<Aresta> like this:

    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 this 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 entry:

5 4
2 3
1 4
2 2
4 3

Here's the output:

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

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

Note that I'm not even bothering to read the value of P here. Its value can be deduced directly from the number of rows read.

    
06.09.2018 / 19:25