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

Faster solution than the previous one (here).

It uses BufferedReader and BufferedWriter instead of Scanner and System.out, respectively. The BufferedWriter change does not have a considerable impact because the output is small.

In addition, some improvements have been done in the Breadth-First Search method.

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) throws NumberFormatException, IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        if (startName.compareTo(finalName) < 0) { // if the first name comes first (alphabetic order)
            bw.write(startName + " " + finalName + " " + biggerDegree + "\n");
        }
        else { // if the second name comes first (alphabetic order)
            bw.write(finalName + " " + startName + " " + biggerDegree + "\n");
        }
      
        bw.flush();
        bw.close();
    }
  
    public static int bfs(String start) {
        Queue<Element> queue = new ArrayDeque<Element>();
        Element e = new Element(start, 0);
        queue.add(e);
      
        HashSet<String> addedToQueue = new HashSet<String>();
        addedToQueue.add(start);
      
        int prevDistance = queue.element().distance;
        while (queue.size() > 0) {
            String current = queue.element().name;
            nameDest = current; // used to get the name of the last person I visited
          
            ArrayList<String> relatives = adjList.get(current);
            for (int i = 0; i < relatives.size(); i++) {
                if (!addedToQueue.contains(relatives.get(i))) {
                    addedToQueue.add(current);
                    e = new Element(relatives.get(i), queue.element().distance+1); // the distance assigned to my neighbor is my_distance+1
                    queue.add(e);
                }
            }
          
            prevDistance = queue.element().distance; // I need to know the previous distance to return it, if necessary
            queue.remove();
        }

        return prevDistance;
    }
  
    public static void checkAdjList(String name1, String name2) {
        if (!adjList.containsKey(name1)) {
            adjList.put(name1, new ArrayList<String>());
        }
        adjList.get(name1).add(name2);
    }
  
    public static void readEntries(BufferedReader br, int numEdges) throws NumberFormatException, IOException {
        for (int i = 0; i < numEdges; i++) {
            String names = br.readLine();
            String[] name = names.split(" ");
          
            checkAdjList(name[0], name[1]);
            checkAdjList(name[1], name[0]);         
        }
    }
  
    public static int reader(BufferedReader br) throws NumberFormatException, IOException {    
        int n;
        int ans = 0;    
     
        while (true) {        
            n = br.read();        
            if (n >= '0' && n <= '9') {
                break;
            }  
        }
          
        while (true) {        
            ans = ans*10 + n-'0';        
            n = br.read();        
            if (n < '0' || n > '9') {
                break;    
            }
        }
     
        return ans;    
    }
  
    public static void process() throws NumberFormatException, IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      
        int numEdges = reader(br);
        readEntries(br, 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);
    }
}

class Element {
    String name;
    int distance;
  
    public Element(String name, int distance) {
        this.name = name;
        this.distance = distance;
    }
}