(UVA) IP-TV - Solution 2

I used Kruskal's algorithm to solve this problem.

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


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

class Main  {
    public static ArrayList<Edge> costs;
    public static HashMap<String, Integer> map;
    public static int[] nodeParent;
    public static int[] depth;
   
    public static int root(int n) {
        while (nodeParent[n] != 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 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 numTests = reader(br);
        for (int i = 0; i < numTests; i++) {
            if (i > 0) {
                System.out.println();
            }
           
            int numCities = reader(br);
            int numLinks = reader(br);
           
            int index = 0;
            String cityStart = "";
            costs = new ArrayList<Edge>();
            map = new HashMap<String, Integer>();
            for (int j = 0; j < numLinks; j++) {
                String line = br.readLine();
                String[] s = line.split("\\s");
               
                String city1 = s[0];
                String city2 = s[1];
                int cost = Integer.parseInt(s[2]);
               
                costs.add(new Edge(city1, city2, cost));
               
                if (!map.containsKey(city1)) {
                    map.put(city1, index++);
                }
                if (!map.containsKey(city2)) {
                    map.put(city2, index++);
                }
            }
            Collections.sort(costs);
           
            nodeParent = new int[numCities];
            depth = new int[numCities];
            for (int j = 0; j < numCities; j++) {
                nodeParent[j] = j;
                depth[j] = 0;
            }
           
            int totalCost = 0;
            for (int j = 0; j < costs.size(); j++) {
                if (union(map.get(costs.get(j).city1), map.get(costs.get(j).city2))) {
                    totalCost += costs.get(j).cost;
                }
            }
           
            System.out.println(totalCost);
        }
               
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

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