(SPOJ) Tarzan - Solution

Link to the problem: http://br.spoj.com/problems/TARZAN12/

The solution below used Union-Find to solve this problem. We connect two vertex if their distance is not more than the distance allowed. Then, in the end, we only check if the number of connections is equal to the number of trees minus one.


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

class solucao {
    public int[] nodeParent;
    public int[] depth;
   
    public int root(int n) {
        while (nodeParent[n] != 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]++;
                }
            }
            else {
                nodeParent[rootN1] = nodeParent[rootN2];
            }
           
            return true;
        }
       
        return false;
    }
   
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        String line = br.readLine();
        String[] s = line.split(" ");
        int numTrees = Integer.parseInt(s[0]);
        int maxDistance = Integer.parseInt(s[1])*Integer.parseInt(s[1]);
       
        Coord[] coords = new Coord[numTrees];       
        for (int i = 0; i < numTrees; i++) {
            line = br.readLine();
            s = line.split(" ");
            int x = Integer.parseInt(s[0]);
            int y = Integer.parseInt(s[1]);
            coords[i] = new Coord(i, x, y); 
        }

        nodeParent = new int[numTrees];
        depth = new int[numTrees];
        for (int i = 0; i < numTrees; i++) {
            nodeParent[i] = i;
            depth[i] = 0;
        }
       
        int countVertex = 0;
        for (int i = 0; i < numTrees; i++) {
            for (int j = i+1; j < numTrees; j++) {
                int d = (coords[i].x-coords[j].x)*(coords[i].x-coords[j].x)+(coords[i].y-coords[j].y)*(coords[i].y-coords[j].y);
                if (d > maxDistance) {
                    continue;
                }
                if (union(i, j)) {
                    countVertex++;               
                }
            }
        }
           
        if (countVertex == numTrees-1) {
            bw.write("S\n");
        }
        else {
            bw.write("N\n");
        }
           
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        solucao m = new solucao();
        m.process();
       
        System.exit(0);
    }
}

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