Задача: 1319. Number of Operations to Make Network Connected
Сложность: medium


Дано n компьютеров, пронумерованных от 0 до n - 1, соединённых Ethernet-кабелями connections, образующими сеть, где connections[i] = [ai, bi] представляет собой соединение между компьютерами ai и bi. Любой компьютер может достичь любого другого компьютера напрямую или косвенно через сеть.

Вам даны начальные соединения сети. Вы можете извлекать определённые кабели между двумя напрямую соединёнными компьютерами и размещать их между любыми парами несоединённых компьютеров, чтобы сделать их напрямую соединёнными.

Верните минимальное количество раз, которое необходимо сделать это, чтобы соединить все компьютеры. Если это невозможно, верните -1.

Пример:

Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.

👨‍💻 Алгоритм:

1⃣Проверьте размер connections. Если он меньше n - 1, у нас недостаточно ребер, чтобы соединить весь граф. В этом случае возвращаем -1.

2⃣Создайте список смежности с помощью connections, где adj[x] содержит всех соседей узла x. Создайте целое число numberOfConnectedComponents, которое хранит количество компонент связности в графе. Инициализируйте его значением 0.

3⃣Создайте массив visit длиной n для отслеживания посещенных узлов. Пройдите по всем узлам, и для каждого узла i проверьте, был ли он посещен. Если узел i не был посещен, увеличьте numberOfConnectedComponents на 1 и начните обход DFS:
Используйте функцию dfs для выполнения обхода. Для каждого вызова передавайте узел, ребра и visit в качестве параметров, начиная с узла i.
Отметьте узел как посещенный.
Пройдитесь по всем соседям узла. Если какой-либо сосед еще не был посещен, рекурсивно вызовите dfs с этим соседом в качестве узла.
Верните numberOfConnectedComponents - 1.

😎 Решение:

class Solution {
    private function dfs($node, $adj, &$visit) {
        $visit[$node] = true;
        if (!isset($adj[$node])) {
            return;
        }
        foreach ($adj[$node] as $neighbor) {
            if (!$visit[$neighbor]) {
                $visit[$neighbor] = true;
                $this->dfs($neighbor, $adj, $visit);
            }
        }
    }

    function makeConnected($n, $connections) {
        if (count($connections) < $n - 1) {
            return -1;
        }

        $adj = [];
        foreach ($connections as $connection) {
            $adj[$connection[0]][] = $connection[1];
            $adj[$connection[1]][] = $connection[0];
        }

        $numberOfConnectedComponents = 0;
        $visit = array_fill(0, $n, false);
        for ($i = 0; $i < $n; $i++) {
            if (!$visit[$i]) {
                $numberOfConnectedComponents++;
                $this->dfs($i, $adj, $visit);
            }
        }

        return $numberOfConnectedComponents - 1;
    }
}

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