Estou fazendo esta questão no URI Online Judge.
Eu estou tentando com DFS, mas atá agora não consegui nada.
Botei uma variável pra marcar até o nível que ela vai e quando chegar nesse nível ela volta, mas está me retornando as saídas erradas.
Estou com dúvida se aqui eu usaria um BFS ou DFS, qual seria melhor? Estou fazendo certo?
package Rerisson_e_o_Churrasco.copy;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.Map.Entry;
/**
* IMPORTANT:
* O nome da classe deve ser "Main" para que a sua solução execute
* Class name must be "Main" for your solution to execute
* El nombre de la clase debe ser "Main" para que su solución ejecutar
*/
public class Main{
int qtdVertice;
int nivel;
Map<String,ArrayList<String>> Ar = new HashMap<>();
public Main(int qtdVertice, int nivel){
this.qtdVertice = qtdVertice;
this.nivel = nivel;
}
public void add_Aresta(String Origem, String Destino){
if(Ar.containsKey(Origem)){
Ar.get(Origem).add(Destino);
}else{
ArrayList<String> a= new ArrayList<>();
a.add(Destino);
Ar.put(Origem,a);
}
}
public int DFS(int contador, String S, ArrayList resposta){
if(!resposta.contains(S))
resposta.add(S);
if(contador == nivel) {
return contador;
}
if(Ar.containsKey(S)) {
for(String a : Ar.get(S)) {
DFS(contador++,a,resposta);
}
}
return contador--;
}
public void DFS_init(String nome) {
int contador = 0;
ArrayList<String> resposta = new ArrayList<>();
DFS(contador, nome, resposta);
resposta.remove(nome);
Collections.sort(resposta);
System.out.println(resposta.size());
for(String b : resposta) {
System.out.println(b);
}
}
public static void main(String arg[]) {
Scanner sc = new Scanner(System.in);
int n;
int G;
String S;
String T;
String inicio = null;
String a[] = new String[2];
a = sc.nextLine().split(" ");
n = Integer.parseInt(a[0]);
G = Integer.parseInt(a[1]);
Main teste = new Main(n,G);
for(int i = 0; i < n; i++){
a = sc.nextLine().split(" ");
S = a[0];
T = a[1];
if(i == 0) {
inicio = S;
}
teste.add_Aresta(S, T);
}
teste.DFS_init(inicio);
}
}