(UVA) Expensive Subway - Solution 1

I used Kruskal's algorithm to solve this problem.


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

class Main {
    public static HashMap<String, Integer> map;
    public static int[] nodeParent;
    public static int[] depth;
   
    public static int count() {
        int[] v = new int[nodeParent.length];
        for (int i = 0; i < nodeParent.length; i++) {
            v[root(nodeParent[i])]++;
        }
       
        int c = 0;
        for (int i = 0; i < v.length; i++) {
            if (v[i] != 0) {
                c++;
            }
        }
       
        return c;
    }
   
    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]++;
                }
            }
            else {
                nodeParent[rootN1] = nodeParent[rootN2];
            }
           
            return true;
        }
       
        return false;
    }
   
    public static void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
       
        int numStations = sc.nextInt();
        int numConnections = sc.nextInt();
        while (numStations != 0 || numConnections != 0) {
            map = new HashMap<String, Integer>();
            for (int i = 0; i < numStations; i++) {
                String name = sc.next();
                map.put(name, i);
            }
           
            Connection[] connections = new Connection[numConnections];
            for (int i = 0; i < numConnections; i++) {
                String station1 = sc.next();
                String station2 = sc.next();
                int cost = sc.nextInt();
               
                connections[i] = new Connection(map.get(station1), map.get(station2), cost);
            }
            Arrays.sort(connections);
           
            int start = map.get(sc.next());
           
            nodeParent = new int[numStations];
            depth = new int[numStations];
            for (int i = 0; i < numStations; i++) {
                nodeParent[i] = i;
                depth[i] = 0;
            }
           
            int totalCost = 0;
            for (int i = 0; i < numConnections; i++) {
                if (union(connections[i].station1, connections[i].station2)) {
                    totalCost += connections[i].cost;
                }
            }
           
            int connectedComponents = count();
           
            if (connectedComponents == 1) {
                System.out.println(totalCost);
            }
            else {
                System.out.println("Impossible");
            }
           
            numStations = sc.nextInt();
            numConnections = sc.nextInt();
        }
                                       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

class Connection implements Comparable<Connection> {
    int station1;
    int station2;
    int cost;
   
    public Connection(int s1, int s2, int c) {
        station1 = s1;
        station2 = s2;
        cost = c;
    }
   
    public int compareTo(Connection c) {
        return this.cost-c.cost;
    }
}