(UVA) Freckles - Solution 1

I used Kruskal's algorithm to solve this problem.

First, I calculate the distance between the freckles. Then, I sort these distances and call the Union-Find method, which will connect the freckles beginning with the smallest distances. The Union-Find method does not allow the code to connect two freckles that are already connected, avoiding cycles and creating a minimum spanning tree.

You can see more about minimum spanning tree here.


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

class Main  {
    public static int[] nodeParent;
    public static int[] depth;
   
    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 double distance(Coord f1, Coord f2) {
        return (f2.x-f1.x)*(f2.x-f1.x)+(f2.y-f1.y)*(f2.y-f1.y);
    }
   
    public static void calcDist(Coord[] freckles, int numFreckles, ArrayList<Dist> distances) {
        for (int i = 0; i < numFreckles; i++) {
            for (int j = i+1; j < numFreckles; j++) {
                distances.add(new Dist(i, j, distance(freckles[i], freckles[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++) {
            if (i > 0) {
                System.out.println(); // blank line between two conseq cases
            }
           
            int numFreckles = sc.nextInt();
            Coord[] freckles = new Coord[numFreckles];
            for (int j = 0; j < numFreckles; j++) {
                double x = sc.nextDouble();
                double y = sc.nextDouble();
                Coord c = new Coord(x, y);
                freckles[j] = c;
            }
           
            ArrayList<Dist> distances = new ArrayList<Dist>();
            calcDist(freckles, numFreckles, distances);
           
            Collections.sort(distances);
           
            nodeParent = new int[numFreckles];
            depth = new int[numFreckles];
            for (int j = 0; j < numFreckles; j++) {
                nodeParent[j] = j;
                depth[j] = 0;
            }
           
            double d = 0.0;
            for (int j = 0; j < distances.size(); j++) {
                if (union(distances.get(j).f1, distances.get(j).f2)) {
                    d += Math.sqrt(distances.get(j).dist);
                }          
            }
           
            System.out.printf("%.2f\n", d);
        }       
                                            
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

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

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