(UVA) X-Plosives - Solution

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

We need to generate the Minimum Spanning Tree (MST) to solve this problem. The answer is the amount of edges that we do not use in our MST.


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

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));
       
        while (sc.hasNext()) {
            ArrayList<Pair> pairs = new ArrayList<>();
           
            int maxNumber = 0;
           
            int n1 = sc.nextInt();
            while (n1 != -1) {
                int n2 = sc.nextInt();
                pairs.add(new Pair(n1, n2));
               
                maxNumber = Math.max(maxNumber, n1);
                maxNumber = Math.max(maxNumber, n2);
               
                n1 = sc.nextInt();
            }
           
            int numRefusals = 0;
            nodeParent = new int[maxNumber+1];
            depth = new int[maxNumber+1];
            for (int i = 0; i < maxNumber+1; i++) {
                nodeParent[i] = i;
                depth[i] = 0;
            }
           
            for (int i = 0; i < pairs.size(); i++) {
                if (!union(pairs.get(i).n1, pairs.get(i).n2)) {
                    numRefusals++;
                }
            }
           
            bw.write(numRefusals+"\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 Pair {
    int n1;
    int n2;
   
    public Pair(int n1, int n2) {
        this.n1 = n1;
        this.n2 = n2;
    }
}