(UVA) Driving Range - Solution 1

I used Kruskal's algorithm to solve this problem.


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

class Main {
    public static Edge[] edges;
    public static int[] nodeParent;
    public static int[] depth;
   
    public static int count(int numCities) {
        int[] v = new int[numCities];
        for (int i = 0; i < numCities; i++) {
            v[root(nodeParent[i])]++;
        }
       
        int c = 0;
        for (int i = 0; i < numCities; i++) {
            if (v[i] > 0) {
                c++;
            }
        }
       
        return c;
    }
   
    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]++;
                }
            }
            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 numCities = reader(br);
        int numRoads = reader(br);
        while (numCities != 0 || numRoads != 0) {
            edges = new Edge[numRoads];
            for (int i = 0; i < numRoads; i++) {
                int c1 = reader(br);
                int c2 = reader(br);
                int cost = reader(br);
               
                edges[i] = new Edge(c1, c2, cost);
            }
           
            Arrays.sort(edges);
           
            nodeParent = new int[numCities];
            depth = new int[numCities];
            for (int i = 0; i < numCities; i++) {
                nodeParent[i] = i;
                depth[i] = 0;
            }
           
            int maxCost = -1;
            for (int i = 0; i < numRoads; i++) {
                if (union(edges[i].city1, edges[i].city2)) {
                    if (edges[i].cost > maxCost) {
                        maxCost = edges[i].cost;
                    }
                }
            }
           
            if (count(numCities) == 1) {
                System.out.println(maxCost);
            }
            else {
                System.out.println("IMPOSSIBLE");
            }
           
            numCities = reader(br);
            numRoads = reader(br);
        }
                                             
        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 city1;
    int city2;
    int cost;
   
    public Edge(int city1, int city2, int cost) {
        this.city1 = city1;
        this.city2 = city2;
        this.cost = cost;
    }
   
    public int compareTo(Edge e) {
        return this.cost-e.cost;
    }
}