(UVA) Frogger - Solution 1

This solution uses Kruskal's algorithm.

First, I read the coordinate of each stone, and I map them to an index. Then, I get the distance from each node to every other node (without repetitions). Finally, with the distances sorted, I use the union-find method to connect two stones. It is important to understand that I always try to connect every two unconnected stones which has the smallest distance. Moreover, if two stones are already connected, I do not need to connect them because it would create a cycle. My condition to stop is if the stone where Freddy is has a connection with the stone where Fiona is.


import java.io.*;
import java.util.*;
import java.text.DecimalFormat;

class Main  {
    public static ArrayList<Distance> distances;
    public static HashMap<Integer, Coord> map;
    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 double union(int n1, int n2, double weight) {
        int rootN1 = root(n1);
        int rootN2 = root(n2);
       
        if (rootN1 != rootN2) { // not connected
            if (depth[rootN1] >= depth[rootN2]) {
                nodeParent[rootN2] = nodeParent[rootN1]; 
                if (depth[rootN1] == depth[rootN2]) {
                    depth[rootN1] += 1;
                }  
            }
            else {
                nodeParent[rootN1] = nodeParent[rootN2];
            }
            return weight;
        }
       
        return -1.0;
    }
   
    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 calcDist(Coord c1, int curr, int numStones) {
        for (int i = curr+1; i < numStones; i++) {
            if (i != curr) {
                Coord c2 = map.get(i);
                double dist = dist(c1, c2);
                Distance d = new Distance(curr, i, dist);
                distances.add(d);
            }
        }
    }
   
    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 numStones = reader(br);
        int numCase = 0;
        while (numStones != 0) {
            distances = new ArrayList<Distance>();
            map = new HashMap<Integer, Coord>();
           
            int index = 0;
            int index2 = 0;
            for (int i = 0; i < numStones; i++) {
                int x = reader(br);
                int y = reader(br);
                Coord c = new Coord(x, y);
                map.put(index++, c);
            }
           
            for (int i = 0; i < numStones; i++) {
                calcDist(map.get(i), i, numStones);
            }
           
            Collections.sort(distances);

            nodeParent = new int[numStones];
            depth = new int[numStones];
            for (int i = 0; i < numStones; i++) {
                nodeParent[i] = i;
                depth[i] = 0;
            }
            double maxWeight = -1.0;
            for (int i = 0; i < distances.size(); i++) {
                double w = union(distances.get(i).source, distances.get(i).dest, distances.get(i).distance);
                if (w > maxWeight) {
                    maxWeight = w;
                }
                if (root(0) == root(1)) {
                    break;
                }
            }

            DecimalFormat df = new DecimalFormat("#.000");
            System.out.println("Scenario #" + ++numCase + "\nFrog Distance = " + df.format(Math.sqrt(maxWeight)) + "\n");
           
            numStones = reader(br);
        }
                 
        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() {
    }
   
    public Coord(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class Distance implements Comparable<Distance> {
    int source;
    int dest;
    double distance;
   
    public Distance(int s, int d, double dist) {
        this.source = s;
        this.dest = d;
        this.distance = dist;
    }
   
    public int compareTo(Distance d) {
        double compareDist = d.distance;
       
        if ((this.distance - compareDist) < 0) {
            return -1;
        }
        else if ((this.distance - compareDist) > 0) {
            return 1;
        }
       
        return 0;
    }
}

class Edge {
    int stone;
    double weight;
   
    public Edge(int s, double w) {
        stone = s;
        weight = w;
    }
}