(UVA) Erdos Numbers - Solution

I used Breadth-First Search to solve this problem.

First, I split the string containing the description of the papers in order to get the names which, after correctly manipulated, are stored in an adjacency list. Then, I read the queries and, for each one of them, I call the BFS method.


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

class Main  {
    public static HashMap<String, ArrayList<String>> adjList;
   
    public static int bfs(String start, String end) {
        Queue<Erdos> queue = new ArrayDeque<Erdos>();
        Erdos e = new Erdos(start, 0);
        queue.add(e);
       
        HashSet<String> addedToQueue = new HashSet<String>();
        addedToQueue.add(start);
       
        while (queue.size() > 0) {
            Erdos curr = queue.poll();
            String currPerson = curr.name;
            int currErdosNum = curr.erdosNum;
           
            if (currPerson.equals(end)) {
                return currErdosNum;
            }
           
            if (adjList.get(currPerson) == null) {
                continue;
            }
           
            ArrayList<String> reachPpl = adjList.get(currPerson);
            for (int i = 0; i < reachPpl.size(); i++) {
                String next = reachPpl.get(i);
                if (!addedToQueue.contains(next)) {
                    e = new Erdos(next, currErdosNum+1);
                    queue.add(e);
                    addedToQueue.add(next);
                }
            }
        }
       
        return -1;
    }
   
    public static void process() throws NumberFormatException, IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      
        String line = br.readLine();
        int numScenarios = Integer.parseInt(line);
        for (int i = 0; i < numScenarios; i++) {
            line = br.readLine();
            String[] s = line.split("\\s");
            int numDescriptions = Integer.parseInt(s[0]);
            int numQueries = Integer.parseInt(s[1]);
           
            adjList = new HashMap<String, ArrayList<String>>();
            for (int j = 0; j < numDescriptions; j++) {
                line = br.readLine();
                s = line.split(":");
                String[] s2 = s[0].split(", ");
                ArrayList<String> names = new ArrayList<String>();
                for (int k = 0; k < s2.length; k += 2) {
                    names.add(s2[k]+", "+s2[k+1]);
                }
                for (int k = 0; k < names.size(); k++) {
                    if (!adjList.containsKey(names.get(k))) {
                        adjList.put(names.get(k), new ArrayList<String>());
                    }
                    for (int l = 0; l < names.size(); l++) {
                        if (l != k) {
                            adjList.get(names.get(k)).add(names.get(l));
                        }
                    }
                }
            }
           
            System.out.println("Scenario " + (i+1));
            for (int j = 0; j < numQueries; j++) {
                String query = br.readLine();
                int erdosNum = bfs(query, "Erdos, P.");
               
                if (erdosNum == -1) {
                    System.out.println(query + " infinity");
                }
                else {
                    System.out.println(query + " " + erdosNum);
                }
            }
           
        }
                                            
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Erdos {
    String name;
    int erdosNum;
   
    public Erdos(String n, int eN) {
        name = n;
        erdosNum = eN;
    }
}