1319. Number of Operations to Make Network Connected
given n компьютеров, пронумерованных от 0 до n - 1, соединённых Ethernet-кабелями connections, образующими сеть, где connections[i] = [ai, bi] представляет собой соединение между компьютерами ai и bi. Любой компьютер может достичь любого другого компьютера напрямую или косвенно через сеть.
Вам given начальные соединения сети. Вы можете извлекать определённые кабели между двумя напрямую соединёнными компьютерами и размещать их между любыми парами несоединённых компьютеров, чтобы сделать их напрямую соединёнными.
return минимальное количество раз, которое необходимо сделать это, чтобы соединить все компьютеры. Если это невозможно, return -1.
Example:
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/originalpublic 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/originalclass 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/originalfunc 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
}Algorithm
Проверьте размер connections. Если он меньше n - 1, у нас недостаточно ребер, чтобы соединить весь graph. В этом случае возвращаем -1.
Создайте список смежности с помощью connections, где adj[x] содержит всех соседей узла x. Создайте integer numberOfConnectedComponents, которое хранит количество компонент связности в graphе. Инициализируйте его значением 0.
Создайте array visit длиной n для отслеживания посещенных узлов. Пройдите по всем узлам, и для каждого узла i проверьте, был ли он посещен. Если узел i не был посещен, увеличьте numberOfConnectedComponents на 1 и начните обход DFS:
Используйте функцию dfs для выполнения обхода. Для каждого вызова передавайте узел, ребра и visit в качестве параметров, начиная с узла i.
Отметьте узел как посещенный.
Пройдитесь по всем соседям узла. Если какой-либо сосед еще не был посещен, рекурсивно вызовите dfs с этим соседом в качестве узла.
return numberOfConnectedComponents - 1.
😎
Vacancies for this task
Active vacancies with overlapping task tags are shown.