(UVA) Arctic Network - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=674&page=show_problem&problem=1310

For this problem, we need to generate the Minimum Spanning Tree (MST) through the distances between every pair of node. Next, we transform some vertexes in satellite channels, and we present the remaining edge with the maximum value.


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

class Main {
    public int[] nodeParent;
    public int[] depth;
   
    public int root(int n) {
        while (n != nodeParent[n]) {
            n = nodeParent[n];
        }
        return n;       
    }
   
    public 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 void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        int numTests = sc.nextInt();
        for (int i = 0; i < numTests; i++) {
            int numSatellite = sc.nextInt();
            int numOutposts = sc.nextInt();
           
            Coord[] coords = new Coord[numOutposts];
            for (int j = 0; j < numOutposts; j++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                coords[j] = new Coord(x, y);
            }
           
            ArrayList<Edge> distances = new ArrayList<>();
            // calculate the distance between every pair of node
            for (int j = 0; j < numOutposts; j++) {
                for (int k = j+1; k < numOutposts; k++) {
                    double distance = (coords[j].x-coords[k].x)*(coords[j].x-coords[k].x)+(coords[j].y-coords[k].y)*(coords[j].y-coords[k].y);
                    distances.add(new Edge(j, k, distance));
                }
            }
           
            Collections.sort(distances);
           
            // apply kruskal
            nodeParent = new int[numOutposts];
            depth = new int[numOutposts];
            for (int j = 0; j < numOutposts; j++) {
                nodeParent[j] = j;
                depth[j] = 0;
            }
           
            int index = 0;
            double[] usedEdges = new double[numOutposts-1];
            for (int j = 0; j < distances.size(); j++) {
                if (union(distances.get(j).n1, distances.get(j).n2)) {
                    usedEdges[index++] = distances.get(j).distance;
                }
            }
           
            DecimalFormat df = new DecimalFormat("#.00");
            // now, I have the best edges, but I still can transform some vertexes in satellite
            bw.write(df.format(Math.sqrt(usedEdges[numOutposts-1-numSatellite]))+"\n");
        }       
                                              
        bw.flush();
        bw.close();
       
        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 Edge implements Comparable<Edge> {
    int n1;
    int n2;
    double distance;
   
    public Edge(int n1, int n2, double d) {
        this.n1 = n1;
        this.n2 = n2;
        distance = d;
    }
   
    public int compareTo(Edge e) {
        if (this.distance-e.distance > 0) {
            return 1;
        }
        else if (this.distance-e.distance < 0) {
            return -1;
        }
        return 0;
    }
}