Dado un grafo no dirigido G con N Nodes, M aristas y un número entero K , la tarea es encontrar la cantidad máxima de aristas que se pueden eliminar de modo que queden exactamente K componentes conectados después de la eliminación de las aristas. Si el gráfico no puede contener componentes de conexión K , imprima -1 .
Ejemplos:
Entrada: N = 4, M = 3, K = 2, Bordes[][] = {{1, 2}, {2, 3}, {3, 4}}
Salida: 1
Explicación:
Una forma posible es eliminar el borde [1, 2]. Entonces habrá 2 componentes de conexión como se muestra a continuación:
Entrada: N = 3, M = 3, K = 3, Bordes[][] = {{1, 2}, {2, 3}, {3, 1}}
Salida: 3
Explicación: Todos los bordes se pueden quitar para hacer 3 componentes conectados como se muestra a continuación:
Enfoque: Para resolver el problema dado, cuente el número de componentes conectados presentes en el gráfico dado . Sea la cuenta C . Observe que si C es mayor que K , entonces ninguna posible eliminación de bordes puede generar K componentes conectados, ya que el número de componentes conectados solo aumentará. De lo contrario, la respuesta siempre existirá.
Es necesario hacer las siguientes observaciones para resolver el problema:
- Supongamos que C 1 , C 2 , …, C c , son el número de Nodes en cada componente conectado. Luego, cada componente debe tener bordes como C 1 – 1, C 2 – 1, …, C c -1 después de quitar los bordes. Por lo tanto,
C 1 – 1 + C 2 – 1 + … + C c – 1 = C 1 + C 2 + … + C c – C = N – C , donde N es el número de Nodes.
- La condición anterior nos dará los componentes conectados a C al eliminar los bordes M – (N – C) ya que se necesitan bordes N – C para hacer componentes C. Para obtener K componentes, (K – C) se deben eliminar más bordes.
- Por lo tanto, el número total de aristas a eliminar viene dado por:
METRO – (N – C) + (K – C) = METRO – N + K
Siga los pasos a continuación para resolver el problema:
- Cuente el número de componentes conectados presentes en el gráfico dado . Sea la cuenta C .
- Si C es mayor que K , imprima -1 .
- De lo contrario, imprima M – N + K donde N es el número f de Nodes, M es el número de aristas y K es el número requerido de componentes conectados.
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;
class Graph
{
public:
int V;
map<int, vector<int>> adj;
Graph(int);
void addEdge(int, int);
void DFS(int, vector<bool> &);
} * g;
// Constructor
Graph::Graph(int V)
{
// No. of vertices
this->V = V;
// Dictionary of lists
for(int i = 1; i <= V; i++)
adj[i] = vector<int>();
}
// Function to add edge
// in the graph
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
adj[w].push_back(v);
}
// Function to perform DFS
void Graph::DFS(int s, vector<bool> &visited)
{
// Create a stack for DFS
stack<int> stack;
// Push the current source node
stack.push(s);
while (!stack.empty())
{
// Pop a vertex from stack
// and print it
s = stack.top();
stack.pop();
// Traverse adjacent vertices
// of the popped vertex s
for(auto node : adj[s])
{
if (!visited[node])
{
// If adjacent is unvisited,
// push it to the stack
visited[node] = true;
stack.push(node);
}
}
}
}
// Function to return the count
// edges removed
void countRemovedEdges(int N, int M, int K)
{
int C = 0;
// Initially mark all vertices
// as not visited
vector<bool> visited(g->V + 1, false);
for(int node = 1; node <= N; node++)
{
// If node is unvisited
if (!visited[node])
{
// Increment Connected
// component count by 1
C = C + 1;
// Perform DFS Traversal
g->DFS(node, visited);
// Print the result
if (C <= K)
cout << M - N + K << endl;
else
cout << -1 << endl;
}
}
}
// Driver Code
int main(int argc, char const *argv[])
{
int N = 4, M = 3, K = 2;
// Create Graph
g = new Graph(N);
// Given Edges
g->addEdge(1, 2);
g->addEdge(2, 3);
g->addEdge(3, 4);
// Function Call
countRemovedEdges(N, M, K);
}
// This code is contributed by sanjeev2552
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG
{
static ArrayList<ArrayList<Integer>> graph;
// Function to perform DFS
static void DFS(int s, boolean[] visited)
{
// Create a stack for DFS
Stack<Integer> stack = new Stack<>();
// Push the current source node
stack.push(s);
while (!stack.isEmpty())
{
// Pop a vertex from stack
// and print it
s = stack.peek();
stack.pop();
// Traverse adjacent vertices
// of the popped vertex s
for(Integer node : graph.get(s))
{
if (!visited[node])
{
// If adjacent is unvisited,
// push it to the stack
visited[node] = true;
stack.push(node);
}
}
}
}
// Function to return the count
// edges removed
static void countRemovedEdges(int N, int M, int K)
{
int C = 0;
// Initially mark all vertices
// as not visited
boolean[] visited = new boolean[N+1];
for(int node = 1; node <= N; node++)
{
// If node is unvisited
if (!visited[node])
{
// Increment Connected
// component count by 1
C = C + 1;
// Perform DFS Traversal
DFS(node, visited);
// Print the result
if (C <= K)
System.out.println(M - N + K);
else
System.out.println(-1);
}
}
}
// Driver code
public static void main (String[] args)
{
int N = 4, M = 3, K = 2;
// Create Graph
graph = new ArrayList<>();
for(int i = 0; i <= N; i++)
graph.add(new ArrayList<Integer>());
// Given Edges
graph.get(1).add(2);
graph.get(2).add(3);
graph.get(3).add(4);
// Function Call
countRemovedEdges(N, M, K);
}
}
// This code is contributed by offbeat.
Python3
# Python3 program for the above approach
class Graph:
# Constructor
def __init__(self, V):
# No. of vertices
self.V = V
# Dictionary of lists
self.adj = {i: [] for i in range(1, V + 1)}
# Function to add edge
# in the graph
def addEdge(self, v, w):
self.adj[v].append(w)
self.adj[w].append(v)
# Function to perform DFS
def DFS(self, s, visited):
# Create a stack for DFS
stack = []
# Push the current source node
stack.append(s)
while (len(stack)):
# Pop a vertex from stack
# and print it
s = stack[-1]
stack.pop()
# Traverse adjacent vertices
# of the popped vertex s
for node in self.adj[s]:
if (not visited[node]):
# If adjacent is unvisited,
# push it to the stack
visited[node] = True
stack.append(node)
# Function to return the count
# edges removed
def countRemovedEdges(N, M, K):
C = 0
# Initially mark all vertices
# as not visited
visited = [False for i in range(g.V + 1)]
for node in range(1, N + 1):
# If node is unvisited
if (not visited[node]):
# Increment Connected
# component count by 1
C = C + 1
# Perform DFS Traversal
g.DFS(node, visited)
# Print the result
if C <= K:
print(M - N + K)
else:
print(-1)
# Driver Code
N, M, K = 4, 3, 2
# Create Graph
g = Graph(N)
# Given Edges
g.addEdge(1, 2)
g.addEdge(2, 3)
g.addEdge(3, 4)
# Function Call
countRemovedEdges(N, M, K)
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG {
static List<List<int>> graph;
// Function to perform DFS
static void DFS(int s, bool[] visited)
{
// Create a stack for DFS
Stack<int> stack = new Stack<int>();
// Push the current source node
stack.Push(s);
while (stack.Count > 0)
{
// Pop a vertex from stack
// and print it
s = (int)stack.Peek();
stack.Pop();
// Traverse adjacent vertices
// of the popped vertex s
foreach(int node in graph[s])
{
if (!visited[node])
{
// If adjacent is unvisited,
// push it to the stack
visited[node] = true;
stack.Push(node);
}
}
}
}
// Function to return the count
// edges removed
static void countRemovedEdges(int N, int M, int K)
{
int C = 0;
// Initially mark all vertices
// as not visited
bool[] visited = new bool[N+1];
for(int node = 1; node <= N; node++)
{
// If node is unvisited
if (!visited[node])
{
// Increment Connected
// component count by 1
C = C + 1;
// Perform DFS Traversal
DFS(node, visited);
// Print the result
if (C <= K)
Console.WriteLine(M - N + K);
else
Console.WriteLine(-1);
}
}
}
// Driver code
static void Main() {
int N = 4, M = 3, K = 2;
// Create Graph
graph = new List<List<int>>();
for(int i = 0; i <= N; i++)
graph.Add(new List<int>());
// Given Edges
graph[1].Add(2);
graph[2].Add(3);
graph[3].Add(4);
// Function Call
countRemovedEdges(N, M, K);
}
}
// This code is contributed by rameshtravel07.
Javascript
<script>
// JavaScript program for the above approach
let graph;
// Function to perform DFS
function DFS(s, visited)
{
// Create a stack for DFS
let stack = [];
// Push the current source node
stack.push(s);
while (stack.length > 0)
{
// Pop a vertex from stack
// and print it
s = stack[stack.length - 1];
stack.pop();
// Traverse adjacent vertices
// of the popped vertex s
for(let node = 0; node < graph[s].length; node++)
{
if (!visited[graph[s][node]])
{
// If adjacent is unvisited,
// push it to the stack
visited[graph[s][node]] = true;
stack.push(graph[s][node]);
}
}
}
}
// Function to return the count
// edges removed
function countRemovedEdges(N, M, K)
{
let C = 0;
// Initially mark all vertices
// as not visited
let visited = new Array(N+1);
visited.fill(false);
for(let node = 1; node <= N; node++)
{
// If node is unvisited
if (!visited[node])
{
// Increment Connected
// component count by 1
C = C + 1;
// Perform DFS Traversal
DFS(node, visited);
// Print the result
if (C <= K)
document.write((M - N + K) + "</br>");
else
document.write(-1 + "</br>");
}
}
}
let N = 4, M = 3, K = 2;
// Create Graph
graph = [];
for(let i = 0; i <= N; i++)
graph.push([]);
// Given Edges
graph[1].push(2);
graph[2].push(3);
graph[3].push(4);
// Function Call
countRemovedEdges(N, M, K);
</script>
Producción:
1
Complejidad temporal: O(N + M)
Espacio auxiliar: O(M + N)
Publicación traducida automáticamente
Artículo escrito por aanchaltiwari y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA