Número máximo de aristas que se eliminarán para contener exactamente K componentes conectados en el gráfico

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 -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:  

  1. Cuente el número de componentes conectados presentes en el gráfico dado . Sea la cuenta C .
  2. Si C es mayor que K , imprima -1 .
  3. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *