(Hacker Rank) Kruskal (MST): Really Special Subtree - Solution

Link to the problem: https://www.hackerrank.com/challenges/kruskalmstrsub

This problem requires to find the minimum spanning tree of the given graphs using Kruskal's algorithm.

Although the problem gives a stating node, the solution below starts using the edge whose weight is the minimum.


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

public class Solution {
    public static ArrayList<Edge> edges;
    public static int[] nodeParent;
    public static int[] depth;
   
    public static int root(int n) {
        while (n != nodeParent[n]) {
            n = nodeParent[n];
        }
        return n;
    }
   
    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] += 1;
                }
            }   
            else {
                nodeParent[rootN1] = nodeParent[rootN2];
            }
            return true;
        }
        return false;
    }
   
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
       
        int numNodes = sc.nextInt();
        int numEdges = sc.nextInt();

        edges = new ArrayList<>();
        for (int i = 0; i < numEdges; i++) {
            int n1 = sc.nextInt();
            int n2 = sc.nextInt();
            int cost = sc.nextInt();
           
            edges.add(new Edge(n1, n2, cost));
        }

        int start = sc.nextInt();
       
        nodeParent = new int[numNodes+1];
        depth = new int[numNodes+1];
        for (int i = 1; i <= numNodes; i++) {
            nodeParent[i] = i;
            depth[i] = 0;
        }
       
        Collections.sort(edges);
        int totalCost = 0;
        for (int i = 0; i < numEdges; i++) {
            if (union(edges.get(i).node1, edges.get(i).node2)) {
                totalCost += edges.get(i).cost;
            }           
        }
       
        System.out.println(totalCost);
    }
}

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