(Hacker Rank) Prim's (MST) : Special Subtree - Solution

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

In order to respect all the properties that are imposed, we need to find the minimum spanning tree to solve this problem, and the title suggests that we use Prim's algorithm.


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

public class Solution {
    public static HashMap<Integer, ArrayList<Edge>> adjList;
   
    public static Comparator<Edge> costComparator = new Comparator<Edge>() {
        public int compare(Edge e1, Edge e2) {
            return e1.cost-e2.cost;
        }   
    };
   
    public static int prim(int start, int numNodes) {
        Queue<Edge> queue = new PriorityQueue<>(numNodes, costComparator);
        queue.add(new Edge(start, 0));
       
        HashSet<Integer> visited = new HashSet<>();
       
        int totalCost = 0;
        while (queue.size() > 0) {
            Edge curr = queue.poll();
            int currNode = curr.node;
            int currCost = curr.cost;
           
            if (visited.contains(currNode)) {
                continue;
            }
            visited.add(currNode);
           
            totalCost += currCost;
            if (visited.size() == numNodes) {
                return totalCost;
            }
           
            ArrayList<Edge> reachNodes = adjList.get(currNode);
            for (int i = 0; i < reachNodes.size(); i++) {
                queue.add(new Edge(reachNodes.get(i).node, reachNodes.get(i).cost));
            }
        }
       
        return -1;
    }
   
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int numNodes = sc.nextInt();
        int numEdges = sc.nextInt();
       
        adjList = new HashMap<>();
        for (int i = 1; i <= numNodes; i++) {
            adjList.put(i, new ArrayList<Edge>());
        }
       
        for (int i = 0; i < numEdges; i++) {
            int n1 = sc.nextInt();
            int n2 = sc.nextInt();
            int c = sc.nextInt();
           
            adjList.get(n1).add(new Edge(n2, c));
            adjList.get(n2).add(new Edge(n1, c));
        }
       
        int start = sc.nextInt();
        System.out.println(prim(start, numNodes));
    }
}

class Edge {
    int node;
    int cost;
   
    public Edge(int n, int c) {
        node = n;
        cost = c;
    }
}