Задача: 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; } } } Ставь 👍 и забирай 📚 Базу знаний