← Static tasks

1319. Number of Operations to Make Network Connected

leetcode medium

#array#csharp#graph#hash-table#leetcode#linked-list#medium#recursion

Task

Дано 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.

C# solution

matched/original
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;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private void Dfs(int node, unordered_map<int, List<int>> adj, bool[] visit) {
        visit[node] = true;
        if (!adj.count(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.size() < n - 1) {
            return -1;
        }
        var adj = new unordered_map<int, List<int>>();
        foreach (var connection in connections) {
            if (!adj.count(connection[0])) {
                adj[connection[0]] = new List<int>();
            }
            if (!adj.count(connection[1])) {
                adj[connection[1]] = new List<int>();
            }
            adj[connection[0]].push_back(connection[1]);
            adj[connection[1]].push_back(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;
    }
}

Java solution

matched/original
class Solution {
    public void dfs(int node, Map<Integer, List<Integer>> adj, boolean[] visit) {
        visit[node] = true;
        if (!adj.containsKey(node)) {
            return;
        }
        for (int neighbor : adj.get(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;
        }

        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int[] connection : connections) {
            adj.computeIfAbsent(connection[0], k -> new ArrayList<Integer>()).add(connection[1]);
            adj.computeIfAbsent(connection[1], k -> new ArrayList<Integer>()).add(connection[0]);
        }

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

        return numberOfConnectedComponents - 1;
    }
}

Go solution

matched/original
func dfs(node int, adj map[int][]int, visit []bool) {
    visit[node] = true
    for _, neighbor := range adj[node] {
        if !visit[neighbor] {
            visit[neighbor] = true
            dfs(neighbor, adj, visit)
        }
    }
}

func makeConnected(n int, connections [][]int) int {
    if len(connections) < n-1 {
        return -1
    }

    adj := make(map[int][]int)
    for _, connection := range connections {
        adj[connection[0]] = append(adj[connection[0]], connection[1])
        adj[connection[1]] = append(adj[connection[1]], connection[0])
    }

    numberOfConnectedComponents := 0
    visit := make([]bool, n)
    for i := 0; i < n; i++ {
        if !visit[i] {
            numberOfConnectedComponents++
            dfs(i, adj, visit)
        }
    }

    return numberOfConnectedComponents - 1
}

Explanation

Algorithm

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

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

Создайте массив visit длиной n для отслеживания посещенных узлов. Пройдите по всем узлам, и для каждого узла i проверьте, был ли он посещен. Если узел i не был посещен, увеличьте numberOfConnectedComponents на 1 и начните обход DFS:

Используйте функцию dfs для выполнения обхода. Для каждого вызова передавайте узел, ребра и visit в качестве параметров, начиная с узла i.

Отметьте узел как посещенный.

Пройдитесь по всем соседям узла. Если какой-либо сосед еще не был посещен, рекурсивно вызовите dfs с этим соседом в качестве узла.

Верните numberOfConnectedComponents - 1.

😎