Сложность: medium
Есть n городов, пронумерованных от 1 до n. Вам даны целое число n и массив connections, где connections[i] = [xi, yi, costi] указывает, что стоимость соединения города xi и города yi (двунаправленное соединение) равна costi.
Верните минимальную стоимость для соединения всех n городов так, чтобы между каждой парой городов был хотя бы один путь. Если невозможно соединить все n городов, верните -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.
👨💻 Алгоритм:
1⃣Сортировка рёбер:
Отсортируйте все соединения (рёбра) в графе по их весам (стоимости) в порядке возрастания.
2⃣Итерация по рёбрам и объединение:
Используйте структуру данных Disjoint Set (Union-Find) для проверки циклов и объединения поддеревьев. Для каждого ребра проверьте, принадлежат ли его концы разным поддеревьям, и если да, объедините их, добавив ребро в минимальное остовное дерево (MST).
3⃣Проверка соединённости:
Подсчитайте количество рёбер в MST. Если оно меньше n-1, верните -1, так как соединить все города невозможно. Иначе верните суммарную стоимость рёбер в MST.
😎 Решение:
class DisjointSet {
private var parent: [Int]
init(_ n: Int) {
parent = Array(0...n)
}
func find(_ x: Int) -> Int {
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}
func union(_ x: Int, _ y: Int) {
let rootX = find(x)
let rootY = find(y)
if rootX != rootY {
parent[rootY] = rootX
}
}
}
class Solution {
func minimumCost(_ n: Int, _ connections: [[Int]]) -> Int {
let sortedConnections = connections.sorted { $0[2] < $1[2] }
let disjointSet = DisjointSet(n)
var totalCost = 0
var edgesUsed = 0
for connection in sortedConnections {
let x = connection[0]
let y = connection[1]
let cost = connection[2]
if disjointSet.find(x) != disjointSet.find(y) {
disjointSet.union(x, y)
totalCost += cost
edgesUsed += 1
if edgesUsed == n - 1 {
return totalCost
}
}
}
return edgesUsed == n - 1 ? totalCost : -1
}
}Ставь 👍 и забирай 📚 Базу знаний