(SPOJ) Árvore Genealógica - Solução 1

import java.io.*;
import java.util.*;

class Main  {
    public static HashMap<String, ArrayList<String>> adjList = new HashMap<String, ArrayList<String>>();
    public static String nameDest = "";
   
    public static void printAnswer(String startName, String finalName, int biggerDegree) {
        if (startName.compareTo(finalName) < 0) { // if the first name comes first (alphabetic order)
            System.out.println(startName + " " + finalName + " " + biggerDegree);
        }
        else { // if the second name comes first (alphabetic order)
            System.out.println(finalName + " " + startName + " " + biggerDegree);
        }
    }
   
    public static int bfs(String start) {
        HashSet<String> visited = new HashSet<String>();

        Queue<String> queue = new LinkedList<String>();
        queue.add(start);
       
        int count = 0;
        Queue<Integer> distance = new LinkedList<Integer>();
        distance.add(count);
       
        int prevDistance = 0;
        while (queue.size() >= 0) {
            if (queue.size() == 0) {
                return prevDistance;
            }
           
            String current = queue.poll();
            nameDest = current; //
           
            if (visited.contains(current)) {
                continue;
            }
            visited.add(current);
           
            ArrayList<String> relatives = adjList.get(current);
            for (int i = 0; i < relatives.size(); i++) {
                if (!visited.contains(relatives.get(i))) {
                    queue.add(relatives.get(i));
                    distance.add(distance.element()+1); // the distance assigned to my neighbor is my_distance+1
                }
            }
           
            prevDistance = distance.remove(); // I need to know the previous distance to return it, if necessary
        }
  
        return -1;
    }
   
    public static void checkAdjList(String name1, String name2) {
        if (!adjList.containsKey(name1)) {
            ArrayList<String> list = new ArrayList<String>();
            list.add(name2);
            adjList.put(name1, list);
        }
        else {
            adjList.get(name1).add(name2);
        }
    }
   
    public static void readEntries(Scanner sc, int numEdges) {
        for (int i = 0; i < numEdges; i++) {
            String name1 = sc.next();
            String name2 = sc.next();
           
            checkAdjList(name1, name2); 
            checkAdjList(name2, name1);          
        }
    }
   
    public static void process() throws NumberFormatException, IOException {   
        Scanner sc = new Scanner(System.in);
       
        int numEdges = sc.nextInt();
        readEntries(sc, numEdges);
                        
        String startName = "";
        String finalName = "";
        int biggerDegree = -1;
        for (String name : adjList.keySet()) {
            int degree = bfs(name);
           
            if (degree > biggerDegree) {
                biggerDegree = degree;
                startName = name;
                finalName = nameDest;
            }
        }
       
        printAnswer(startName, finalName, biggerDegree);
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

Comments

Popular posts from this blog

(Coderbyte) Powers of Two - Solução

(Coderbyte) Dash Insert II - Solução

(CoderByte) Number Search - Solução