Сложность: medium
Задача: 1135. Connecting Cities With Minimum Cost

Есть 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 $parent;

    public function __construct($n) {
        $this->parent = range(0, $n);
    }

    public function find($x) {
        if ($this->parent[$x] !== $x) {
            $this->parent[$x] = $this->find($this->parent[$x]);
        }
        return $this->parent[$x];
    }

    public function union($x, $y) {
        $rootX = $this->find($x);
        $rootY = $this->find($y);
        if ($rootX !== $rootY) {
            $this->parent[$rootY] = $rootX;
        }
    }
}

class Solution {
    function minimumCost($n, $connections) {
        usort($connections, function($a, $b) {
            return $a[2] - $b[2];
        });

        $disjointSet = new DisjointSet($n);
        $totalCost = 0;
        $edgesUsed = 0;

        foreach ($connections as $connection) {
            list($x, $y, $cost) = $connection;
            if ($disjointSet->find($x) !== $disjointSet->find($y)) {
                $disjointSet->union($x, $y);
                $totalCost += $cost;
                $edgesUsed++;
                if ($edgesUsed === $n - 1) {
                    return $totalCost;
                }
            }
        }
        return $edgesUsed === $n - 1 ? $totalCost : -1;
    }
}

Ставь 👍 и забирай 📚 Базу знаний