(UVA) Transportation System - Solution 1

I used Kruskal's algorithm to solve this problem.


import java.io.*;
import java.util.*;
import java.lang.Math;

class Main {
    public static Coord[] cities;
    public static ArrayList<Distance> distances;
    public static int[] nodeParent;
    public static int[] depth;
   
    public static int root(int n) {
        int currN = n;
        while (nodeParent[currN] != currN) {
            currN = nodeParent[currN];
        }
       
        return currN;
    }
   
    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 double dist(Coord c1, Coord c2) {
        return (c1.x-c2.x)*(c1.x-c2.x)+(c1.y-c2.y)*(c1.y-c2.y);
    }
   
    public static void calcDistances(int numCities) {
        for (int i = 0; i < numCities; i++) {
            for (int j = i+1; j < numCities; j++) {
                distances.add(new Distance(i, j, dist(cities[i], cities[j])));
            }
        }
    }
   
    public static void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
       
        int numCases = sc.nextInt();
        for (int i = 0; i < numCases; i++) {
            int numCities = sc.nextInt();
            int lengthTwoCities = sc.nextInt();
            cities = new Coord[numCities];
            for (int j = 0; j < numCities; j++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                cities[j] = new Coord(x, y);
            }
           
            distances = new ArrayList<Distance>();
            calcDistances(numCities);
           
            Collections.sort(distances);
           
            nodeParent = new int[numCities];
            depth = new int[numCities];
            for (int j = 0; j < numCities; j++) {
                nodeParent[j] = j;
                depth[j] = 0;
            }
           
            int numStates = 1;
            double doubleExtensionRoads = 0.0;
            double doubleExtensionRailroads = 0.0;
            for (int j = 0; j < distances.size(); j++) {
                if (union(distances.get(j).point1, distances.get(j).point2)) {
                    double dist = Math.sqrt(distances.get(j).dist);
                    if (dist <= lengthTwoCities) {
                        doubleExtensionRoads += dist;
                    }
                    else {
                        numStates++;
                        doubleExtensionRailroads += dist;
                    }
                }
            }
           
            System.out.println("Case #" + (i+1) + ": " + numStates + " " + Math.round(doubleExtensionRoads) + " " + Math.round(doubleExtensionRailroads));
        }
                               
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

class Coord {
    int x;
    int y;
   
    public Coord(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class Distance implements Comparable<Distance> {
    int point1;
    int point2;
    double dist;
   
    public Distance(int point1, int point2, double dist) {
        this.point1 = point1;
        this.point2 = point2;
        this.dist = dist;
    }
   
    public int compareTo(Distance d) {
        if (this.dist-d.dist < 0) {
            return -1;
        }
        else if (this.dist-d.dist > 0) {
            return 1;
        }
       
        return 0;
    }
}