0
I’m making this issue in the URI Online Judge.
I’m trying with DFS, but until now I got nothing.
I put a variable to mark up to the level she goes and when she gets to this level she comes back, but it’s returning me the wrong exits.
I’m wondering if here I would use a BFS or DFS, which one would be better? I’m doing it right?
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);
}
}