Problem Related to graphs

Question

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


        }

    }

Answer 1

The text of the problem explains that friends will be selected according to the level away from Rerisson. In other words, there has to be at most n edges between Rerisson and the selected persons.

A Width Search (BFS) explores the entire level before moving on to the next one. An in-depth search (DFS), on the other hand, explores an entire branch before moving on to the next. This makes it clear that you need to implement a wide search to solve the problem in question.

I’ll leave a pseudocode with the algorithm so anyone can understand how it works.

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
}