(SPOJ) Rede ótica - Solution 2

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

In order to solve this problem, I used Prim's algorithm.

While reading the edges, I store them in an adjacency list. Then, I call the Prim method, which choose the next edge to be examined according to its cost.


import java.io.*;
import java.util.*;
import java.text.DecimalFormat;

class Main  {
    public static HashMap<Integer, ArrayList<Edge>> adjList;

    public static Comparator<Edge> costComparator = new Comparator<Edge>() {
        public int compare(Edge e1, Edge e2) {
            if ((e1.cost - e2.cost) < 0) {
                return -1;
            }
            else if ((e1.cost - e2.cost) > 0) {
                return 1;
            }
           
            return 0;
        }
    };
   
    public static ArrayList<Points> prim(int start, int numPoints) {
        Queue<Edge> queue = new PriorityQueue<Edge>(numPoints, costComparator);
        Edge e = new Edge(0, start, 0);
        queue.add(e);
       
        HashSet<Integer> visited = new HashSet<Integer>();
       
        ArrayList<Points> points = new ArrayList<Points>();
       
        int countPoints = 0;
        while (queue.size() > 0) {
            Edge currPath = queue.poll();
            int currFrom = currPath.source;
            int currPoint = currPath.dest;
            int currCost = currPath.cost;
           
            if (visited.contains(currPoint)) {
                continue;
            }
            visited.add(currPoint);
           
            if (countPoints > 0) {
                Points p = new Points(currFrom, currPoint);
                points.add(p);
            }
            countPoints += 1;
            if (countPoints == numPoints) {
                return points;
            }
           
            ArrayList<Edge> reachPoints = adjList.get(currPoint);
            for (int i = 0; i < reachPoints.size(); i++) {
                Edge next = reachPoints.get(i);
                e = new Edge(currPoint, next.dest, next.cost);
                queue.add(e);
            }
        }
       
        return points;
    }
   
    public static int reader(BufferedReader br) throws NumberFormatException, IOException {     
        int n;
        int resp = 0;     
      
        while (true) {         
            n = br.read();         
            if (n >= '0' && n <= '9') {
                break;
            }
        }
           
        while (true) {         
            resp = resp*10 + n-'0';         
            n = br.read();         
            if (n < '0' || n > '9') {
                break;     
            }
        }
      
        return resp;     
    }
       
    public static void process() throws NumberFormatException, IOException {   
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        int countTest = 0;
       
        int numPoints = reader(br);
        int numPaths = reader(br);
        while (numPoints != 0 || numPaths != 0) {
            adjList = new HashMap<Integer, ArrayList<Edge>>();
            for (int i = 0; i < numPoints; i++) {
                adjList.put(i+1, new ArrayList<Edge>());
            }
           
            for (int i = 0; i < numPaths; i++) {
                int p1 = reader(br);
                int p2 = reader(br);
                int cost = reader(br);
                Edge e = new Edge(p1, p2, cost);
                adjList.get(p1).add(e);
                e = new Edge(p2, p1, cost);
                adjList.get(p2).add(e);
            }
       
            System.out.println("Teste " + ++countTest);
            ArrayList<Points> list = prim(1, numPoints);
            for (int i = 0; i < list.size(); i++) {
                if (list.get(i).dest > list.get(i).source) {
                    System.out.println(list.get(i).source + " " + list.get(i).dest);
                }
                else {
                    System.out.println(list.get(i).dest + " " + list.get(i).source);
                }
            }
            System.out.println();
           
            numPoints = reader(br);
            numPaths = reader(br);
        }
                         
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Edge {
    int source;
    int dest;
    int cost;
   
    public Edge(int s, int d, int c) {
        source = s;
        dest = d;
        cost = c;
    }
}

class Points {
    int source;
    int dest;
   
    public Points(int s, int d) {
        source = s;
        dest = d;
    }
}