Задача: 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.

😎 Решение:

public class Solution {
    private void Dfs(int node, Dictionary<int, List<int>> adj, bool[] visit) {
        visit[node] = true;
        if (!adj.ContainsKey(node)) {
            return;
        }
        foreach (int neighbor in adj[node]) {
            if (!visit[neighbor]) {
                visit[neighbor] = true;
                Dfs(neighbor, adj, visit);
            }
        }
    }

    public int MakeConnected(int n, int[][] connections) {
        if (connections.Length < n - 1) {
            return -1;
        }

        var adj = new Dictionary<int, List<int>>();
        foreach (var connection in connections) {
            if (!adj.ContainsKey(connection[0])) {
                adj[connection[0]] = new List<int>();
            }
            if (!adj.ContainsKey(connection[1])) {
                adj[connection[1]] = new List<int>();
            }
            adj[connection[0]].Add(connection[1]);
            adj[connection[1]].Add(connection[0]);
        }

        int numberOfConnectedComponents = 0;
        bool[] visit = new bool[n];
        for (int i = 0; i < n; i++) {
            if (!visit[i]) {
                numberOfConnectedComponents++;
                Dfs(i, adj, visit);
            }
        }

        return numberOfConnectedComponents - 1;
    }
}

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