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]
A:
就是经典的minimum spanning tree, 用Prim or Kruskal
但是没有用Union_by rank .而只是随机union了
class Solution { public: int minimumCost(int N, vector<vector<int>>& connections) { sort(connections.begin(), connections.end(), [](const vector<int>& a, const vector<int>& b) { return a[2] < b[2]; }); // make set for (int i = 1; i <= N; i++) { parent[i] = i; } int res = 0; int edgeCount = 0; for (auto edge : connections) { int city1 = edge[0]; int city2 = edge[1]; if (find_set(city1) != find_set(city2)) { union_set(city1, city2); // merge their parent edgeCount++; res += edge[2]; // cost } if (edgeCount == N - 1) { return res; } } return -1; } private: unordered_map<int, int> parent; int find_set(int city) { if (parent[city] != city) { parent[city] = find_set(parent[city]); } return parent[city]; } void union_set(int city1, int city2) { parent[find_set(city1)] = parent[find_set(city2)]; } };
这个题,以前没有做过,需要多多熟悉