Connecting Cities With Minimum Cost

Similar Problems:

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.

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.

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]

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution:

// Blog link: https://code.dennyzhang.com/connecting-cities-with-minimum-cost // Basic Ideas: unionfind + minimum spanning tree // // The more than one island, return -1 // For valid ones, sort connections // Loop connections from small to big // If two nodes not connected, add this path to the result // // Complexity: Time O(n*log(n)), Space O(n) import "sort" var cnt int type UF struct { parent []int } func constructor(size int) UF { cnt = size parent := make([]int, size) for i, _ := range parent { parent[i] = i } return UF{parent:parent} } func (uf *UF) union (i, j int) bool { n1, n2 := uf.find(i), uf.find(j) if n1 == n2 { return false } uf.parent[n2] = n1 cnt-- return true } func (uf *UF) find (x int) int { l := []int{} for x != uf.parent[x] { l = append(l, x) x = uf.parent[x] } // path compression for _, v := range l { uf.parent[v] = x } return x } func minimumCost(N int, connections [][]int) int { if len(connections) < N-1 { return -1 } sort.Slice(connections, func(i, j int) bool { return connections[i][2] < connections[j][2] }) uf := constructor(N) res := 0 for _, item := range connections { if uf.union(item[0]-1, item[1]-1) { res += item[2] } } if cnt != 1 { return -1 } else { return res } }