Java | LeetCode
Задача: 1135. Connecting Cities With Minimum Cost
Сложность: 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 int[] parents;
public void Union(int a, int b) {
int rootA = Find(a);
int rootB = Find(b);
if (rootA == rootB) return;
this.parents[rootB] = rootA;
}
public int Find(int a) {
while (a != this.parents[a]) {
a = this.parents[a];
}
return a;
}
public boolean isInSameGroup(int a, int b) {
return Find(a) == Find(b);
}
public DisjointSet(int N) {
this.parents = new int[N + 1];
for (int i = 1; i <= N; ++i) {
this.parents[i] = i;
}
}
}
Ставь 👍 и забирай 📚 Базу знаний
1 · 420 ·