(UVA) ACM Contest and Blackout - Solution

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

For this problem, we need to generate the Minimum Spanning Tree (MST) to find the minimum cost to connect all the schools. The solution below opted by using Kruskal's algorithm. When we calculate the minimum cost, we need to keep all the edges used for this purpose. Finally, we need to generate a MST for every edge that we considered for the minimum cost, but without using that specific edge. For every minimum cost encountered, we keep the one that is minimum.

PS.: It is important to remember that when we are calculating the second minimum cost, we need to check if all the schools are being considered.


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

class Main {
    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 {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        int numTests = sc.nextInt();
        for (int i = 0; i < numTests; i++) {
            int numSchools = sc.nextInt();
            int numConnections = sc.nextInt();
           
            Connection[] connections = new Connection[numConnections];
            for (int j = 0; j < numConnections; j++) {
                int s1 = sc.nextInt();
                int s2 = sc.nextInt();
                int cost = sc.nextInt();
               
                connections[j] = new Connection(s1, s2, cost);
            }
           
            Arrays.sort(connections);
           
            nodeParent = new int[numSchools+1];
            depth = new int[numSchools+1];
            for (int j = 0; j < numSchools+1; j++) {
                nodeParent[j] = j;
                depth[j] = 0;
            }
           
            int minCost = 0;
            boolean first = true;
            ArrayList<Integer> considered = new ArrayList<>();
            // find the first minimum cost;
            for (int j = 0; j < numConnections; j++) {
                if (union(connections[j].s1, connections[j].s2)) {
                    minCost += connections[j].cost;                             
                    considered.add(j);
                }
            }
           
           
            int secondMinCost = Integer.MAX_VALUE;
            // apply kruskal again
            // for every kruskal here, disconsider one of the edges used for the minimum cost
            for (int j = 0; j < considered.size(); j++) {
                nodeParent = new int[numSchools+1];
                depth = new int[numSchools+1];
                for (int k = 0; k < numSchools+1; k++) {
                    nodeParent[k] = k;
                    depth[k] = 0;
                }
               
                int totalCost = 0;
                int numConsidered = 1; // I always have one node that will be connected to the others through union-find
                for (int k = 0; k < numConnections; k++) {
                    if (k == considered.get(j)) {
                        continue;
                    }
                    if (union(connections[k].s1, connections[k].s2)) {
                        totalCost += connections[k].cost;  
                        numConsidered++;                          
                    }
                }
                if (numConsidered == numSchools) {
                    secondMinCost = Math.min(secondMinCost, totalCost);
                }
            }
           
            bw.write(minCost + " " + secondMinCost + "\n");
        }       
                                              
        bw.flush();
        bw.close();
       
        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 s1;
    int s2;
    int cost;
   
    public Connection(int s1, int s2, int cost) {
        this.s1 = s1;
        this.s2 = s2;
        this.cost = cost;
    }
   
    public int compareTo(Connection c) {
        return this.cost-c.cost;
    }
}