Ajuda para entender a questão Ciclovias da OBI 2016 Nível Sênior/Universitário

Programação Java
#1

Olá à todos.,

Estou tendo dificuldade para resolver uma questão da Olimpíada brasileira de Informática fase 2 de 2016, é a última questão desse pdf: https://olimpiada.ic.unicamp.br/static/extras/obi2016/provas/ProvaOBI2016_f2pu.pdf

import java.util.Scanner;

public class solucao {

public static int[] organizaValores(String linha) {

  String[] semEspaco = linha.split("\\s+");

  return new int[] {
  	Integer.parseInt(semEspaco[0]),
  	Integer.parseInt(semEspaco[1])
  };

}

static int[][] entradas;
static int m,n;
static int[] saida;

public static void main(String[] args) {
//entrada

  Scanner in = new Scanner(System.in);

  String linha1 = in.nextLine();

  int[] array1 = organizaValores(linha1);

  n = array1[0];
  m = array1[1];

  entradas = new int[m][2];

  for (int i = 0; m > i; i++) {

  	String linhaNova = in.nextLine();

  	int[] arrayNovo = organizaValores(linhaNova);

  	entradas[i] = new int[]{arrayNovo[0], arrayNovo[1]};
  }

//processamento

  saida = new int[n];

  for (int i = 0; n > i; i++) {
  	saida[i] = 0;
  }

  //saida
  for (int i = 0; n > i; i++) {
  	System.out.print(saida[i] + (i == n-1 ? "" : " "));
  }

}

}

Basicamente o que só consegui fazer de “certo”.
O que eu entendi sobre a questão é:
Ele dá um mapa pela entrada dizendo quais intersecções tem ciclovias entre elas e na saída é esperado o maior número possível de intersecções por qual ele passa(ele chama isso de maior caminho possível) para cada intersecção que ele existe.

No exemplo 1 da questão ele dá esses dados:

5 5 (número de intersecções(variável “n”) e número de ruas(variável “m”) )
1 5 (as próximas “m” linhas são duas intersecções em que há uma ciclovia)
1 3
1 2
2 5
4 5

E a saída é uma única linha com os números:
4 4 4 2 2

Em uma das minhas tentativas(usando o exemplo 1) achei que dava para fazer caminhos automáticos por tentativa e erro(não vou mostrar esse código porque ficou enorme e “feio”, além de dar errado, mas a lógica dele é essa abaxo):
Se o mapa fosse um gráfico assim(os traços seriam as ciclovias):
3
|
1-5-4
| |
2-
E os caminhos tentados ficariam assim, para o primeiro número da saída, iniciando na intersecção 1:
1-2-5-4(tamanho seria 4)
1-3 (tamanho seria 2)
1-5-4 (tamanho seria 3)
1-5-2 (tamanho seria 3)
Logo, o maior caminho seria o de maior tamanho.
O maior caminho deve ser uma sequência crescente para os números pares e impares.
Só que quando testei iniciando com a intersecção 3, não passava de tamanho 1.

No site da OBI achei dois exemplos de resposta em C++(https://olimpiada.ic.unicamp.br/passadas/OBI2016/fase2/programacao/) mas não consegui entender muita coisa já que só sei Java(por enquanto).

Não sei o que não entendi direito, faz dias que estou tentado solucionar isso(acho que nem me considero programador mais :sob: :sweat_smile:).

O que faço?