1135. Connecting Cities With Minimum Cost

Kruskal Algorithm:

Union-Find and + sort edge by height, add edge if not connected

time: union-find for each vertex: O(1), total O(E); sort array: ElogE.

total O(ElogE+E)

space: O(V)

// Some code
class Solution {
    int[] graph;
    int count;
    int cost;
    public int minimumCost(int n, int[][] connections) {
        graph = new int[n+1];
        for(int i=0; i<graph.length; i++){
            graph[i]=i;
        }
        count = n+1;
        
        Arrays.sort(connections, (a,b)->a[2]-b[2]);
        
        for(int[] edge : connections){
            if(!connected(edge[0], edge[1])){
                union(edge[0], edge[1]);
                cost+=edge[2];
            }
        }
        
        return count == 2 ? cost : -1;
    }
    
    private void union(int p, int q){
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP!=rootQ){
            graph[rootP] = rootQ;
            count--;
        }
    }
    
    private boolean connected(int p, int q){
        int rootP = find(p);
        int rootQ = find(q);
        return rootP==rootQ;
    }
    
    private int find(int p){
        while(graph[p]!=p){
            graph[p]=graph[graph[p]];
            p=graph[p];
        }
        return p;
    }
}