(UVA) Re-connecting Computer Sites - Solution 2

I used Kruskal's algorithm to solve this problem.

If you want to see another solution for this problem, click here.


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

class Main  {
    public static ArrayList<Edge> costs;
    public static int[] nodeParent;
    public static int[] depth;
   
    public static int root(int n) {
        while (nodeParent[n] != n) {
            n = nodeParent[n];
        }
       
        return n;
    }
   
    public static boolean union(int n1, int n2) {
        int rootN1 = root(n1);
        int rootN2 = root(n2);
       
        if (rootN1 != rootN2) {
            if (depth[rootN1] >= depth[rootN2]) {
                nodeParent[rootN2] = nodeParent[rootN1];
                if (depth[rootN1] == depth[rootN2]) {
                    depth[rootN1] += 1;
                }
            }
            else {
                nodeParent[rootN1] = nodeParent[rootN2];
            }
           
            return true;
        }
       
        return false;
    }
   
    public static void readEntry(BufferedReader br) throws NumberFormatException, IOException {
        int comp1 = reader(br);
        int comp2 = reader(br);
        int cost = reader(br);
       
        costs.add(new Edge(comp1, comp2, 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();
            }
           
            costs = new ArrayList<Edge>();

            int numComputers = reader(br);
           
            for (int i = 0; i < (numComputers-1); i++) {
                readEntry(br);
            }
            nodeParent = new int[numComputers+1];
            depth = new int[numComputers+1];
            for (int i = 1; i <= numComputers; i++) {
                nodeParent[i] = i;
                depth[i] = 0;
            }
            int oldCost = 0;
            Collections.sort(costs);
            for (int i = 0; i < costs.size(); i++) {
                if (union(costs.get(i).computer1, costs.get(i).computer2)) {
                    oldCost += costs.get(i).cost;
                }           
            }

            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 = 0;
            Collections.sort(costs);
            for (int i = 1; i <= numComputers; i++) {
                nodeParent[i] = i;
                depth[i] = 0;
            }
            for (int i = 0; i < costs.size(); i++) {
                if (union(costs.get(i).computer1, costs.get(i).computer2)) {
                    newCost += costs.get(i).cost;
                }           
            }
                         
            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 implements Comparable<Edge> {
    int computer1;
    int computer2;
    int cost;
   
    public Edge(int computer1, int computer2, int cost) {
        this.computer1 = computer1;
        this.computer2 = computer2;
        this.cost = cost;
    }
   
    public int compareTo(Edge e) {
        return this.cost-e.cost;
    }
}