(UVA) Airports - Solution

In order to solve this problem, I used Kruskal's algorithm.

After reading the edges, I sort them. If the cost of the road is smaller than the cost to build an airport, I call the Union-Find method to connect the locations.
Finally, I count how many connected components I have, and this value is correspondent to the quantity of airports, which help me to give the answer.


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

class Main  {
    public static int[] nodeParent;
    public static int[] depth;
   
    public static int countComponents(int numLocations) {
        int[] vector = new int[numLocations+1];
        for (int i = 1; i <= numLocations; i++) {
            vector[root(nodeParent[i])] = 1;
        }
       
        int count = 0;
        for (int i = 1; i <= numLocations; i++) {
            if (vector[i] == 1) {
                count++;
            }
        }
       
        return count;
    }
   
    public static int root(int n) {
        int currNode = n;
        while (nodeParent[currNode] != currNode) {
            currNode = nodeParent[currNode];
        }
       
        return currNode;
    }
   
    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 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 numTests = reader(br);
        for (int i = 0; i < numTests; i++) {
            int numLocations = reader(br);
            int numRoads = reader(br);
            int costAirport = reader(br);
           
            int index = 0;
            Road[] roads = new Road[numRoads];
            for (int j = 0; j < numRoads; j++) {
                int locX = reader(br);
                int locY = reader(br);
                int cost = reader(br);
               
                Road r = new Road(locX, locY, cost);
                roads[index++] = r;
            }
           
            Arrays.sort(roads);
           
            nodeParent = new int[numLocations+1];
            depth = new int[numLocations+1];
            for (int j = 1; j <= numLocations; j++) {
                nodeParent[j] = j;
                depth[j] = 0;
            }
           
            int costRoads = 0;
            for (int j = 0; j < numRoads; j++) {
                if (roads[j].cost < costAirport) {
                    if (union(roads[j].source, roads[j].dest)) {
                        costRoads += roads[j].cost;
                    }
                }
            }
           
            int numAirports = countComponents(numLocations);
           
            System.out.println("Case #" + (i+1) + ": " + (numAirports*costAirport+costRoads) + " " + numAirports);
        }
                         
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Road implements Comparable<Road> {
    int source;
    int dest;
    int cost;
   
    public Road(int s, int d, int c) {
        source = s;
        dest = d;
        cost = c;
    }
   
    public int compareTo(Road r) {
        return this.cost - r.cost;
    }
}