(UVA) Oreon - Solution 1

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3649

We want to determine a set of tunnels which has the least cost. Then, we can use a Minimum Spanning Tree to solve this problem.


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

class Main {
    public ArrayList<Edge> list;
    public int[] nodeParent;
    public int[] depth;
   
    public int root(int n) {
        while (n != nodeParent[n]) {
            n = nodeParent[n];
        }
        return n;
    }
   
    public 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 void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int numTests = Integer.parseInt(br.readLine());
        for (int test = 0; test < numTests; test++) {
            int numCities = Integer.parseInt(br.readLine());

            list = new ArrayList<>();           
            for (int i = 0; i < numCities; i++) {
                String line = br.readLine();
                line = line.replace(" ", "");
                String[] s = line.split(",");
                for (int j = 0; j < numCities; j++) {
                    if (Integer.parseInt(s[j]) == 0) {
                        continue;
                    }
                    list.add(new Edge(i, j, Integer.parseInt(s[j])));
                }               
            }
            Collections.sort(list);
           
            nodeParent = new int[numCities];
            depth = new int[numCities];
            for (int i = 0; i < numCities; i++) {
                nodeParent[i] = i;
                depth[i] = 0;
            }
           
            System.out.println("Case " + (test+1) + ":");
            for (int i = 0; i < list.size(); i++) {
                if (union(list.get(i).city1, list.get(i).city2)) {
                    System.out.println((char)(list.get(i).city1+'A') + "-" + (char)(list.get(i).city2+'A') + " " + list.get(i).cost);
                }
            }
           
        }
                                                      
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

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