Question

Formatted question description: https://leetcode.ca/all/1135.html

 1135. Connecting Cities With Minimum Cost

 There are N cities numbered from 1 to N.

 You are given connections, where each connections[i] = [city1, city2, cost] represents the cost to connect city1 and city2 together.
 (A connection is bidirectional: connecting city1 and city2 is the same as connecting city2 and city1.)

 Return the minimum cost so that for every pair of cities, there exists a path of connections (possibly of length 1) that connects those two cities together.
 The cost is the sum of the connection costs used. If the task is impossible, return -1.


 Example 1:

 Input: N = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
 Output: 6
 Explanation:
 Choosing any 2 edges will connect all cities so we choose the minimum 2.


 Example 2:

 Input: N = 4, connections = [[1,2,3],[3,4,4]]
 Output: -1
 Explanation:
 There is no way to connect all cities even if all edges are used.


 Note:
     1 <= N <= 10000
     1 <= connections.length <= 10000
     1 <= connections[i][0], connections[i][1] <= N
     0 <= connections[i][2] <= 10^5
     connections[i][0] != connections[i][1]

Algorithm

Kruskal algorithm

This problem is a standard minimum spanning tree problem. There are two solutions: Prim and Kruskal algorithms.

There are two general solutions to the MST (Minimum Spanning Tree) problem. Prim algorithm is one of them. It constructs an MST from the point of view. The general idea is: Let the set of vertices in the graph G be U, first Arbitrarily choose a point in the graph G as the starting point a, add this point to the set V, and then find another point b from the set UV to make the weight of any point from b to V the smallest, then add point b to the set V ; And so on, the current set V={a,b}, and then find another point c from the set UV so that the weight of any point from c to V is the smallest, at this time point c is added to the set V until all vertices All were added to V, and an MST was constructed at this time. Because there are N vertices, the MST has N-1 edges. Each time a point is added to the set V, it means that an MST edge is found.

The Kruskal algorithm is based on the idea of ​​greed. First, we arrange all edges from smallest to largest according to their weights, and then select each edge in order. If the two endpoints of this edge do not belong to the same set, then merge them until all the points belong to the same set Until the collection. As for how to merge into a collection, then here we can use a tool and search collection. In other words, the Kruskal algorithm is a greedy algorithm based on union search.

Code

Java

public class Connecting_Cities_With_Minimum_Cost {

    class Solution {
        public int minimumCost(int N, int[][] connections) {
            Arrays.sort(connections, (a, b) -> a[2]-b[2]);

            int res = 0;
            UF uf = new UF(N);
            for(int [] connect : connections){
                if(uf.find(connect[0]) != uf.find(connect[1])){
                    uf.union(connect[0], connect[1]);
                    res += connect[2];
                }

                if(uf.count == 1){
                    return res;
                }
            }

            return -1;
        }
    }

    class UF{
        int [] parent;
        int [] size;
        int count;

        public UF(int n){
            parent = new int[n+1];
            size = new int[n+1];
            for(int i = 0; i<=n; i++){
                parent[i] = i;
                size[i] = 1;
            }

            this.count = n;
        }

        public int find(int i){
            if(i != parent[i]){
                parent[i] = find(parent[i]);
            }

            return parent[i];
        }

        public void union(int p, int q){
            int i = find(p);
            int j = find(q);
            if(size[i] > size[j]){
                parent[j] = i;
                size[i] += size[j];
            }else{
                parent[i] = j;
                size[j] += size[i];
            }

            this.count--;
        }
    }
}

All Problems

All Solutions