0

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);


        }

    }

1 Resposta 1

0

O texto do problema explica que os amigos serão selecionados de acordo com o nível de distância em relação ao Rerisson. Em outras palavras, tem que haver no máximo n arestas entre o Rerisson e as pessoas selecionadas.

Uma busca em largura (BFS) explora o nível inteiro antes de partir para o próximo. Uma busca em profundidade (DFS), por outro lado, explora um galho inteiro antes de partir para o próximo. Isso torna claro que é preciso implementar uma busca em largura para resolver o problema em questão.

Vou deixar um pseudocódigo com o algoritmo para que qualquer um possa entender o funcionamento.

função busca_em_largura (nodo_raiz, nivel_maximo) {
    abertos := fila
    niveis := fila
    fechados := conjunto

    adicionar nodo_raiz em abertos
    adicionar 0 em niveis

    enquanto há elementos abertos {
        atual := pop em abertos
        nivel := pop em niveis

        para cada vizinho do atual {
            se fechados não contém vizinho e abertos não contém vizinho e nivel < nivel_maximo {
                adicionar vizinho em abertos
                adicionar nivel+1 em niveis
            }
        }

        adicionar atual em fechados
    }

    retornar fechados
}

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .