1135

1135. Connecting Cities With Minimum Cost (Medium)

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.

 

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.

 

Constraints:

• 1 <= n <= 104
• 1 <= connections.length <= 104
• connections[i].length == 3
• 1 <= xi, yi <= n
• xi != yi
• 0 <= costi <= 105

Companies:
Amazon

Related Topics:
Union Find, Graph, Heap (Priority Queue), Minimum Spanning Tree

Similar Questions:

• Minimum Cost to Reach City With Discounts (Medium)

Solution 1. Minimum Spanning Tree - Kruskal

// OJ: https://leetcode.com/problems/connecting-cities-with-minimum-cost/
// Author: github.com/lzl124631x
// Time: O(ElogE)
// Space: O(N)
class UnionFind {
    vector<int> id;
    int cnt; 
public:
    UnionFind(int n) : id(n), cnt(n) {
        iota(begin(id), end(id), 0);
    }
    int find(int a) {
        return id[a] == a ? a : (id[a] = find(id[a]));
    }
    void connect(int a, int b) {
        int p = find(a), q = find(b);
        if (p == q) return;
        --cnt;
        id[p] = q;
    }
    bool connected(int a, int b) {
        return find(a) == find(b);
    }
    int getCount() { return cnt; }
};
class Solution {
public:
    int minimumCost(int n, vector<vector<int>>& E) {
        sort(begin(E), end(E), [](auto &a, auto &b) { return a[2] < b[2]; });
        UnionFind uf(n);
        int ans = 0;
        for (auto &e : E) {
            int u = e[0] - 1, v = e[1] - 1;
            if (uf.connected(u, v)) continue;
            uf.connect(u, v);
            ans += e[2];
        }
        return uf.getCount() == 1 ? ans : -1;
    }
};