# 1135. Connecting Cities With Minimum Cost
###### tags: `Union Find`, `Amazon OA`

Description:
There are n cities labeled from `1` to `n`. You are given the integer `n` and an array `connections` where `connections[i] = [xi, yi, costi]` indicates that the cost of connecting city `xi` and city `yi` (bidirectional connection) is `costi`.

Return the minimum cost to connect all the n cities such that there is at least one path between each pair of cities. If it is impossible to connect all the n cities, return `-1`,

The cost is the sum of the connections' costs used

**Amazon OA:**
*Input:*
* Number of the node `n`.
* A list of edges `connections` where `connection[i] = ["xi", "yi", costi]`.

*Output:*
* Return the list of the edges `result`, where `result[i] = ["xi", "yi", costi]`.

Solution(LeetCode):

* Kruskal

class Solution {
    private int find(int x, int[] parent) {
        if (parent[x] != x) {
            x = find(parent[x], parent);
        }
        return x;
    }
    
    public int minimumCost(int n, int[][] connections) {
        Arrays.sort(connections, (a, b) -> a[2] - b[2]);
        int[] parent = new int[n + 1];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        int cost = 0;
        for (int[] edge: connections) {
            int n1 = find(edge[0], parent);
            int n2 = find(edge[1], parent);
            if (n1 != n2) {
                parent[n1] = n2;
                cost += edge[2];
                n--;
            }
        }
        return n == 1? cost: -1;
    }
}