(UVA) Re-connecting Computer Sites - Solution 1

I used Prim's algorithm to solve this problem.


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

class Main  {
    public static HashMap<Integer, ArrayList<Edge>> adjList;
   
    public static Comparator<Edge> compareCost = new Comparator<Edge>() {
        public int compare(Edge e1, Edge e2) {
            return e1.cost-e2.cost;
        }
    };
   
    public static int prim(int start, int numComputers) {
        Queue<Edge> queue = new PriorityQueue<Edge>(numComputers, compareCost);
        queue.add(new Edge(start, 0));
       
        HashSet<Integer> visited = new HashSet<Integer>();
       
        int totalCost = 0;
        while (queue.size() > 0) {
            Edge curr = queue.poll();
            int currComputer = curr.computer;
            int currCost = curr.cost;
           
            if (visited.contains(currComputer)) {
                continue;
            }
            visited.add(currComputer);

            totalCost += currCost;
            if (visited.size() == numComputers) {
                return totalCost;
            }
           
            ArrayList<Edge> reachComputers = adjList.get(currComputer);
            for (int i = 0; i < reachComputers.size(); i++) {
                queue.add(new Edge(reachComputers.get(i).computer, reachComputers.get(i).cost));
            }
        }
       
        return -1;
    }
   
    public static void readEntry(BufferedReader br) throws NumberFormatException, IOException {
        int comp1 = reader(br);
        int comp2 = reader(br);
        int cost = reader(br);
       
        adjList.get(comp1).add(new Edge(comp2, cost));
        adjList.get(comp2).add(new Edge(comp1, cost));
    }
   
    public static int reader(BufferedReader br) throws NumberFormatException, IOException {     
        int n;
        int resp = 0;     
      
        while (true) {         
            n = br.read();         
            if (n >= '0' && n <= '9') {
                break;
            }
        }
           
        while (true) {         
            resp = resp*10 + n-'0';         
            n = br.read();         
            if (n < '0' || n > '9') {
                break;     
            }
        }
      
        return resp;     
    }
   
    public static void process() throws NumberFormatException, IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int index = 0;
        String line;
               
        do {
            if (index > 0) {
                System.out.println();
            }
           
            adjList = new HashMap<Integer, ArrayList<Edge>>();

            int numComputers = reader(br);
            for (int i = 0; i < numComputers; i++) {
                adjList.put((i+1), new ArrayList<Edge>());
            }
           
            for (int i = 0; i < (numComputers-1); i++) {
                readEntry(br);
            }
            int oldCost = prim(1, numComputers);

            int newAdditionalLines = reader(br);
            for (int i = 0; i < newAdditionalLines; i++) {
                readEntry(br);
            }

            int numOriginalLines = reader(br);
            for (int i = 0; i < numOriginalLines; i++) {
                readEntry(br);
            }

            int newCost = prim(1, numComputers);
                         
            System.out.println(oldCost + "\n" + newCost);
       
            index++;
            line = br.readLine();
        } while (line != null);
                                         
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Edge {
    int computer;
    int cost;
   
    public Edge(int computer, int cost) {
        this.computer = computer;
        this.cost = cost;
    }
}