(UVA) Galactic Bonding - Solution

In order to solve this problem, I implemented the Weighted Quick-Union.

First, I calculate the distance between every node (star) to the others. Then, if the distance between two stars is not more than the given distance, I connect the stars. Finally, in order to know the number of constellations, I need to know how many components I have.

Although I have studied about Union-Find in the class "Algorithms, Part I", from Coursera (you can find more details here and here), I used my own implementation to solve this problem.


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

class Main  { 
    public static Coord[] coordinates;
    public static int[] nodeParent;
    public static int[] depth;
   
    public static int count() {
        int[] v = new int[nodeParent.length];
       
        for (int i = 1; i < nodeParent.length; i++) {
            v[root(nodeParent[i])] += 1;
        }
       
        int c = 0;
        for (int i = 1; i < v.length; i++) {
            if (v[i] != 0) {
                c++;
            }
        }
       
        return c;
    }
   
    public static int root(int node) {
        int currNode = node;
        while (nodeParent[currNode] != currNode) {
            currNode = nodeParent[currNode];
        }
       
        return currNode;
    }
   
    public static void union(int node1, int node2) {
        int rootNode1 = root(node1);
        int rootNode2 = root(node2);
       
        if (rootNode1 != rootNode2) { // they are not connected
            if (depth[rootNode1] >= depth[rootNode2]) {
                nodeParent[rootNode2] = nodeParent[rootNode1];
                if (depth[rootNode1] == depth[rootNode2]) {
                    depth[rootNode1] += 1; // the link between rootNode1 and rootNode2
                }
            }
            else {
                nodeParent[rootNode1] = nodeParent[rootNode2];
            }
        }
    }
   
    public static double calcDistance(Coord coord1, Coord coord2) {
        double x = (coord1.x - coord2.x)*(coord1.x - coord2.x);
        double y = (coord1.y - coord2.y)*(coord1.y - coord2.y);
        double d = x+y;

        return d;
    }
   
    public static void readCoordinates(Scanner sc, int numStars) {
        for (int j = 1; j <= numStars; j++) {
            double x = sc.nextFloat();
            double y = sc.nextFloat();
            coordinates[j] = new Coord(x, y);
        }
    }
   
    public static void initArrays(int numStars) {
        for (int j = 1; j <= numStars; j++) {
            nodeParent[j] = j;
            depth[j] = 0;
        }
    }
   
    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 numStars = sc.nextInt();
            double distance = sc.nextFloat();
            double distancePow = distance*distance;
           
            coordinates = new Coord[numStars+1];
            nodeParent = new int[numStars+1];
            depth = new int[numStars+1];
           
            initArrays(numStars);
           
            readCoordinates(sc, numStars);
                       
            for (int j = 1; j <= numStars; j++) {
                for (int k = j+1; k <= numStars; k++) {
                    if (calcDistance(coordinates[j], coordinates[k]) <= distancePow) {
                        union(j, k);
                    }
                }
            }
           
            System.out.println("Case " + (i+1) + ": " + count());
        }
               
        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;
    }
}