(UVA) Heavy Cycle Edges - Solution 1

I used Kruskal's algorithm to solve this problem.


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

class Main  {
    public static ArrayList<Edge> listEdges;
    public static ArrayList<Integer> costCycles;
    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 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 static void process() throws NumberFormatException, IOException {  
        Scanner sc = new Scanner(System.in);
       
        int numNodes = sc.nextInt();
        int numEdges = sc.nextInt();
        while (numNodes != 0 || numEdges != 0) {
            listEdges = new ArrayList<Edge>();
            for (int i = 0; i < numEdges; i++) {
                int n1 = sc.nextInt();
                int n2 = sc.nextInt();
                int cost = sc.nextInt();
                Edge e = new Edge(n1, n2, cost);
                listEdges.add(e);
            }
           
            Collections.sort(listEdges);
           
            nodeParent = new int[numNodes];
            depth = new int[numNodes];
            for (int i = 0; i < numNodes; i++) {
                nodeParent[i] = i;
                depth[i] = 0;
            }
           
            costCycles = new ArrayList<Integer>();
            for (int i = 0; i < numEdges; i++) {
                if (!union(listEdges.get(i).n1, listEdges.get(i).n2)) {
                    costCycles.add(listEdges.get(i).cost);
                }
            }
           
            if (costCycles.size() > 0) {
                for (int i = 0; i < costCycles.size()-1; i++) {
                    System.out.print(costCycles.get(i) + " ");
                }
                System.out.println(costCycles.get(costCycles.size()-1));
            }
            else {
                System.out.println("forest");
            }
           
            numNodes = sc.nextInt();
            numEdges = sc.nextInt();
        }
                                                
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Edge implements Comparable<Edge> {
    int n1;
    int n2;
    int cost;
   
    public Edge(int n1, int n2, int cost) {
        this.n1 = n1;
        this.n2 = n2;
        this.cost = cost;
    }
   
    public int compareTo(Edge e) {
        return this.cost-e.cost;
    }
}