Problem Related to graphs

0

I am doing this question in URI Online Judge .

I'm trying with DFS, but by now I did not get anything.

I put a variable to mark it up to the level it goes and when it reaches that level it comes back, but it is returning the wrong outputs.

I'm wondering if I'd use a BFS or DFS here, which would be better? Am I 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);


        }

    }
    
asked by anonymous 14.09.2018 / 14:19

1 answer

0

The problem text explains that friends will be selected according to the level distance from Rerisson. In other words, there must be at most n edges between Rerisson and the people selected.

A Boundary Scan (BFS) scans the entire level before moving on to the next level. An in-depth search (DFS), on the other hand, scans an entire branch before departing for the next. This makes it clear that you need to implement a width 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
}
    
06.11.2018 / 14:18