Dado un número entero N , que denota el número de computadoras conectadas por cables que forman una red y una array 2D connections[][] , con cada fila (i, j) representando una conexión entre la i -ésima y la j -ésima computadora, la tarea es conectar todas las computadoras, ya sea directa o indirectamente, eliminando cualquiera de las conexiones dadas y conectando dos computadoras desconectadas.
Si no es posible conectar todas las computadoras, imprima -1 .
De lo contrario, imprima el número mínimo de tales operaciones requeridas.
Ejemplos:
Entrada: N = 4, conexiones[][] = {{0, 1}, {0, 2}, {1, 2}}
Salida: 1
Explicación: Retire la conexión entre las computadoras 1 y 2 y conecte las computadoras 1 y 3.Entrada: N = 5, conexiones[][] = {{0, 1}, {0, 2}, {3, 4}, {2, 3}}
Salida: 0
Enfoque: la idea es utilizar un concepto similar al del árbol de expansión mínimo , ya que en un gráfico con N Nodes, solo se requieren N – 1 bordes para conectar todos los Nodes.
Bordes redundantes = Bordes totales – [(Número de Nodes – 1) – (Número de componentes – 1)]
Si Bordes redundantes > (Número de componentes – 1): Está claro que hay suficientes cables que se pueden usar para conectar computadoras desconectadas. De lo contrario, imprima -1.
Siga los pasos a continuación para resolver el problema:
- Inicialice un mapa desordenado , diga adj para almacenar la lista de adyacencia de la información dada sobre los bordes.
- Inicialice un vector de tipo de datos booleano , digamos visitado , para almacenar si un Node es visitado o no.
- Genere la lista de adyacencia y también calcule el número de aristas.
- Inicialice una variable, digamos components , para almacenar el recuento de componentes conectados .
- Recorra los Nodes del gráfico usando DFS para contar el número de componentes conectados y almacenarlo en los componentes variables .
- Inicialice una variable, digamos redundante , y almacene la cantidad de bordes redundantes usando la fórmula anterior.
- Si los bordes redundantes > componentes – 1 , entonces el número mínimo de operaciones requeridas es igual a componentes – 1 . De lo contrario, imprima -1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to visit the nodes of a graph
void DFS(unordered_map<int, vector<int> >& adj,
int node, vector<bool>& visited)
{
// If current node is already visited
if (visited[node])
return;
// If current node is not visited
visited[node] = true;
// Recurse for neighbouring nodes
for (auto x : adj[node]) {
// If the node is not visited
if (visited[x] == false)
DFS(adj, x, visited);
}
}
// Utility function to check if it is
// possible to connect all computers or not
int makeConnectedUtil(int N,
int connections[][2],
int M)
{
// Stores whether a
// node is visited or not
vector<bool> visited(N, false);
// Build the adjacency list
unordered_map<int, vector<int> > adj;
// Stores count of edges
int edges = 0;
// Building adjacency list
// from the given edges
for (int i = 0; i < M; ++i) {
// Add edges
adj[connections[i][0]].push_back(
connections[i][1]);
adj[connections[i][1]].push_back(
connections[i][0]);
// Increment count of edges
edges += 1;
}
// Stores count of components
int components = 0;
for (int i = 0; i < N; ++i) {
// If node is not visited
if (visited[i] == false) {
// Increment components
components += 1;
// Perform DFS
DFS(adj, i, visited);
}
}
// At least N - 1 edges are required
if (edges < N - 1)
return -1;
// Count redundant edges
int redundant = edges - ((N - 1)
- (components - 1));
// Check if components can be
// rearranged using redundant edges
if (redundant >= (components - 1))
return components - 1;
return -1;
}
// Function to check if it is possible
// to connect all the computers or not
void makeConnected(int N, int connections[][2], int M)
{
// Stores counmt of minimum
// operations required
int minOps = makeConnectedUtil(
N, connections, M);
// Print the minimum number
// of operations required
cout << minOps;
}
// Driver Code
int main()
{
// Given number of computers
int N = 4;
// Given set of connections
int connections[][2] = {
{ 0, 1 }, { 0, 2 }, { 1, 2 }
};
int M = sizeof(connections)
/ sizeof(connections[0]);
// Function call to check if it is
// possible to connect all computers or not
makeConnected(N, connections, M);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to visit the nodes of a graph
public static void DFS(HashMap<Integer, ArrayList<Integer> > adj,
int node, boolean visited[])
{
// If current node is already visited
if (visited[node])
return;
// If current node is not visited
visited[node] = true;
// Recurse for neighbouring nodes
for (int x : adj.get(node)) {
// If the node is not visited
if (visited[x] == false)
DFS(adj, x, visited);
}
}
// Utility function to check if it is
// possible to connect all computers or not
public static int
makeConnectedUtil(int N, int connections[][], int M)
{
// Stores whether a
// node is visited or not
boolean visited[] = new boolean[N];
// Build the adjacency list
HashMap<Integer, ArrayList<Integer> > adj
= new HashMap<>();
// Initialize the adjacency list
for (int i = 0; i < N; i++) {
adj.put(i, new ArrayList<Integer>());
}
// Stores count of edges
int edges = 0;
// Building adjacency list
// from the given edges
for (int i = 0; i < M; ++i) {
// Get neighbours list
ArrayList<Integer> l1
= adj.get(connections[i][0]);
ArrayList<Integer> l2
= adj.get(connections[i][0]);
// Add edges
l1.add(connections[i][1]);
l2.add(connections[i][0]);
// Increment count of edges
edges += 1;
}
// Stores count of components
int components = 0;
for (int i = 0; i < N; ++i) {
// If node is not visited
if (visited[i] == false) {
// Increment components
components += 1;
// Perform DFS
DFS(adj, i, visited);
}
}
// At least N - 1 edges are required
if (edges < N - 1)
return -1;
// Count redundant edges
int redundant
= edges - ((N - 1) - (components - 1));
// Check if components can be
// rearranged using redundant edges
if (redundant >= (components - 1))
return components - 1;
return -1;
}
// Function to check if it is possible
// to connect all the computers or not
public static void
makeConnected(int N, int connections[][], int M)
{
// Stores counmt of minimum
// operations required
int minOps = makeConnectedUtil(N, connections, M);
// Print the minimum number
// of operations required
System.out.println(minOps);
}
// Driver Code
public static void main(String[] args)
{
// Given number of computers
int N = 4;
// Given set of connections
int connections[][]
= { { 0, 1 }, { 0, 2 }, { 1, 2 } };
int M = connections.length;
// Function call to check if it is
// possible to connect all computers or not
makeConnected(N, connections, M);
}
}
// This code is contributed by kingash.
Python3
# Python3 code for the above approach
# Function to visit the nodes of a graph
def DFS(adj, node, visited):
# If current node is already visited
if (visited[node]):
return
# If current node is not visited
visited[node] = True
# Recurse for neighbouring nodes
if(node in adj):
for x in adj[node]:
# If the node is not visited
if (visited[x] == False):
DFS(adj, x, visited)
# Utility function to check if it is
# possible to connect all computers or not
def makeConnectedUtil(N, connections, M):
# Stores whether a
# node is visited or not
visited = [False for i in range(N)]
# Build the adjacency list
adj = {}
# Stores count of edges
edges = 0
# Building adjacency list
# from the given edges
for i in range(M):
# Add edges
if (connections[i][0] in adj):
adj[connections[i][0]].append(
connections[i][1])
else:
adj[connections[i][0]] = []
if (connections[i][1] in adj):
adj[connections[i][1]].append(
connections[i][0])
else:
adj[connections[i][1]] = []
# Increment count of edges
edges += 1
# Stores count of components
components = 0
for i in range(N):
# If node is not visited
if (visited[i] == False):
# Increment components
components += 1
# Perform DFS
DFS(adj, i, visited)
# At least N - 1 edges are required
if (edges < N - 1):
return -1
# Count redundant edges
redundant = edges - ((N - 1) - (components - 1))
# Check if components can be
# rearranged using redundant edges
if (redundant >= (components - 1)):
return components - 1
return -1
# Function to check if it is possible
# to connect all the computers or not
def makeConnected(N, connections, M):
# Stores counmt of minimum
# operations required
minOps = makeConnectedUtil(N, connections, M)
# Print the minimum number
# of operations required
print(minOps)
# Driver Code
if __name__ == '__main__':
# Given number of computers
N = 4
# Given set of connections
connections = [ [ 0, 1 ], [ 0, 2 ], [ 1, 2 ] ]
M = len(connections)
# Function call to check if it is
# possible to connect all computers or not
makeConnected(N, connections, M)
# This code is contributed by ipg2016107
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to visit the nodes of a graph
public static void DFS(Dictionary<int, List<int>> adj, int node, bool[] visited)
{
// If current node is already visited
if (visited[node])
return;
// If current node is not visited
visited[node] = true;
// Recurse for neighbouring nodes
foreach(int x in adj[node]) {
// If the node is not visited
if (visited[x] == false)
DFS(adj, x, visited);
}
}
// Utility function to check if it is
// possible to connect all computers or not
public static int makeConnectedUtil(int N, int[,] connections, int M)
{
// Stores whether a
// node is visited or not
bool[] visited = new bool[N];
// Build the adjacency list
Dictionary<int, List<int>> adj = new Dictionary<int, List<int>>();
// Initialize the adjacency list
for (int i = 0; i < N; i++) {
adj[i] = new List<int>();
}
// Stores count of edges
int edges = 0;
// Building adjacency list
// from the given edges
for (int i = 0; i < M; ++i) {
// Get neighbours list
List<int> l1 = adj[connections[i,0]];
List<int> l2 = adj[connections[i,0]];
// Add edges
l1.Add(connections[i,1]);
l2.Add(connections[i,0]);
// Increment count of edges
edges += 1;
}
// Stores count of components
int components = 0;
for (int i = 0; i < N; ++i) {
// If node is not visited
if (visited[i] == false) {
// Increment components
components += 1;
// Perform DFS
DFS(adj, i, visited);
}
}
// At least N - 1 edges are required
if (edges < N - 1)
return -1;
// Count redundant edges
int redundant = edges - ((N - 1) - (components - 1));
// Check if components can be
// rearranged using redundant edges
if (redundant >= (components - 1))
return components - 1;
return -1;
}
// Function to check if it is possible
// to connect all the computers or not
public static void makeConnected(int N, int[,] connections, int M)
{
// Stores counmt of minimum
// operations required
int minOps = makeConnectedUtil(N, connections, M);
// Print the minimum number
// of operations required
Console.WriteLine(minOps);
}
static void Main() {
// Given number of computers
int N = 4;
// Given set of connections
int[,] connections
= { { 0, 1 }, { 0, 2 }, { 1, 2 } };
int M = connections.GetLength(0);
// Function call to check if it is
// possible to connect all computers or not
makeConnected(N, connections, M);
}
}
// This code is contributed by decode2207.
Javascript
<script>
// Javascript program for the above approach
// Function to visit the nodes of a graph
function DFS(adj, node, visited)
{
// If current node is already visited
if (visited[node])
return;
// If current node is not visited
visited[node] = true;
// Recurse for neighbouring nodes
for(let x = 0; x < adj[node].length; x++) {
// If the node is not visited
if (visited[adj[node][x]] == false)
DFS(adj, adj[node][x], visited);
}
}
// Utility function to check if it is
// possible to connect all computers or not
function makeConnectedUtil(N, connections, M)
{
// Stores whether a
// node is visited or not
let visited = new Array(N);
visited.fill(false);
// Build the adjacency list
let adj = new Map();
// Initialize the adjacency list
for (let i = 0; i < N; i++) {
adj[i] = [];
}
// Stores count of edges
let edges = 0;
// Building adjacency list
// from the given edges
for (let i = 0; i < M; ++i) {
// Get neighbours list
let l1 = adj[connections[i][0]];
let l2 = adj[connections[i][0]];
// Add edges
l1.push(connections[i][1]);
l2.push(connections[i][0]);
// Increment count of edges
edges += 1;
}
// Stores count of components
let components = 0;
for (let i = 0; i < N; ++i) {
// If node is not visited
if (visited[i] == false) {
// Increment components
components += 1;
// Perform DFS
DFS(adj, i, visited);
}
}
// At least N - 1 edges are required
if (edges < N - 1)
return -1;
// Count redundant edges
let redundant = edges - ((N - 1) - (components - 1));
// Check if components can be
// rearranged using redundant edges
if (redundant >= (components - 1))
return components - 1;
return -1;
}
// Function to check if it is possible
// to connect all the computers or not
function makeConnected(N, connections, M)
{
// Stores counmt of minimum
// operations required
let minOps = makeConnectedUtil(N, connections, M);
// Print the minimum number
// of operations required
document.write(minOps);
}
// Given number of computers
let N = 4;
// Given set of connections
let connections = [ [0, 1], [0, 2], [1, 2] ];
let M = connections.length;
// Function call to check if it is
// possible to connect all computers or not
makeConnected(N, connections, M);
// This code is contributed by sureh07.
</script>
Producción:
1
Complejidad temporal: O(N + M)
Espacio auxiliar: O(N)