Задача: 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 {
    func dfs(_ node: Int, _ adj: [Int: [Int]], _ visit: inout [Bool]) {
        visit[node] = true
        guard let neighbors = adj[node] else { return }
        for neighbor in neighbors {
            if !visit[neighbor] {
                visit[neighbor] = true
                dfs(neighbor, adj, &visit)
            }
        }
    }

    func makeConnected(_ n: Int, _ connections: [[Int]]) -> Int {
        if connections.count < n - 1 {
            return -1
        }

        var adj = [Int: [Int]]()
        for connection in connections {
            adj[connection[0], default: []].append(connection[1])
            adj[connection[1], default: []].append(connection[0])
        }

        var numberOfConnectedComponents = 0
        var visit = [Bool](repeating: false, count: n)
        for i in 0..<n {
            if !visit[i] {
                numberOfConnectedComponents += 1
                dfs(i, adj, &visit)
            }
        }

        return numberOfConnectedComponents - 1
    }
}

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