(UVA) Heavy Cycle Edges - Solution 2

If you want to see another solution for this problem, click here.

I used Prim's algorithm to solve this problem.


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

class Main  {
    public static HashMap<Integer, ArrayList<Edge>> adjList;
    public static HashSet<Integer> visited;
    public static int[][] costEdges;
   
    public static Comparator<EdgeWithParent> costComparator = new Comparator<EdgeWithParent>() {
        public int compare(EdgeWithParent e1, EdgeWithParent e2) {
            return e1.e.cost-e2.e.cost;
        }
    };
   
    public static void prim(int start, int numNodes) {
        Queue<EdgeWithParent> queue = new PriorityQueue<EdgeWithParent>(numNodes, costComparator);
        EdgeWithParent ewp = new EdgeWithParent(new Edge(start, 0), start);
        queue.add(ewp);
       
        int numNodesVisited = 0;
        while (queue.size() > 0) {
            EdgeWithParent curr = queue.poll();
            int currNode = curr.e.n;
            int currCost = curr.e.cost;
            int currParent = curr.parent;
           
            if (visited.contains(currNode)) {
                continue;
            }
            visited.add(currNode);
            costEdges[currNode][currParent] = -1;
            costEdges[currParent][currNode] = -1;
           
            numNodesVisited++;
            if (numNodesVisited == numNodes) {
                return;
            }
           
            ArrayList<Edge> reachNodes = adjList.get(currNode);
            for (int i = 0; i < reachNodes.size(); i++) {
                Edge next = reachNodes.get(i);
                ewp = new EdgeWithParent(next, currNode);
                queue.add(ewp);
            }
        }
       
        return;
    }
   
    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) {
            adjList = new HashMap<Integer, ArrayList<Edge>>();
            costEdges = new int[numNodes][numNodes];
            for (int i = 0; i < numNodes; i++) {
                adjList.put(i, new ArrayList<Edge>());
                for (int j = 0; j < numNodes; j++) {
                    costEdges[i][j] = -1;
                }
            }
           
            for (int i = 0; i < numEdges; i++) {
                int n1 = sc.nextInt();
                int n2 = sc.nextInt();
                int cost = sc.nextInt();
                Edge e = new Edge(n2, cost);
                adjList.get(n1).add(e);
                e = new Edge(n1, cost);
                adjList.get(n2).add(e);
                costEdges[n1][n2] = cost;
                costEdges[n2][n1] = cost;
            }
           
            visited = new HashSet<Integer>();
            for (int i = 0; i < numNodes; i++) { // It is possible to have more than one connected component
                if (!visited.contains(i)) {
                    prim(i, numNodes);
                }
            }
           
            ArrayList<Integer> costCycles = new ArrayList<Integer>();
            for (int i = 0; i < numNodes; i++) {
                for (int j = i+1; j < numNodes; j++) {
                    if (costEdges[i][j] >= 0) {
                        costCycles.add(costEdges[i][j]);
                    }
                }
            }
           
            Collections.sort(costCycles);
            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 {
    int n;
    int cost;
   
    public Edge(int n, int cost) {
        this.n = n;
        this.cost = cost;
    }
}

class EdgeWithParent {
    Edge e;
    int parent;
   
    public EdgeWithParent(Edge e, int parent) {
        this.e = e;
        this.parent = parent;
    }
}