Dado un gráfico no dirigido que consta de N valorado en el rango [1, N] tal que los vértices (i, i + 1) están conectados y una array arr[] que consta de M pares de enteros , la tarea es encontrar el número mínimo de bordes que deben eliminarse del gráfico de modo que no exista ninguna ruta para cada par (u, v) en la array arr[] .
Ejemplos:
Entrada: arr[] = {{1, 4}, {2, 5}
Salida: 1
Explicación:
Para N = 5, el gráfico dado se puede representar como:1 <-> 2 <-> 3 <-> 4 <-> 5
Después de eliminar el borde entre los vértices 2 y 3 o el borde entre los vértices 3 y 4, el gráfico se modifica a:
1 <-> 2 3 <-> 4 <-> 5
Ahora, no existe ninguna ruta entre cada par de Nodes en la array. Por lo tanto, el número mínimo de bordes que deben eliminarse es 1.
Entrada: arr[] = {{1, 8}, {2, 7}, {3, 5}, {4, 6}, {7, 9}}
Salida: 2
Enfoque: el problema dado se puede resolver utilizando un enfoque codicioso . La idea es ordenar la array dada de pares arr[] en orden creciente de pares finales y para cada par, digamos (u, v) eliminar los bordes más cercanos conectados al vértice v para que todos los demás vértices en los componentes conectados que contienen el vértice v es inalcanzable. Siga los pasos a continuación para resolver el problema dado:
- Cree una variable, digamos minEdges como 0 , que almacene el recuento de bordes eliminados.
- Cree una variable accesible como 0 , que realice un seguimiento del vértice más pequeño que sea accesible desde el último vértice, es decir, N .
- Ordene la array dada de pares arr[] en orden creciente del segundo valor de los pares .
- Atraviese la array dada arr[] y para cada par (u, v) en arr[] , si es accesible > u , implica que no existe una ruta entre u y v , de lo contrario, se elimina el último borde entre (v – 1) y v es la opción más óptima. Por lo tanto, incremente el valor de minEdges en 1 y el valor de alcanzable será igual a v .
- Después de completar los pasos anteriores, imprima el valor de minEdges como resultado.
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;
// Comparator function to sort the
// given array of pairs in increasing
// order of second value of the pairs
bool comp(pair<int, int> a, pair<int, int> b)
{
if (a.second < b.second) {
return true;
}
return false;
}
// Function to find minimum number of edges
// to be removed such that there exist no
// path between each pair in the array arr[]
int findMinEdges(vector<pair<int, int> > arr,
int N)
{
// Stores the count of edges to be deleted
int minEdges = 0;
// Stores the smallest vertex reachable
// from the current vertex
int reachable = 0;
// Sort the array arr[] in increasing
// order of the second value of the pair
sort(arr.begin(), arr.end(), comp);
// Loop to iterate through array arr[]
for (int i = 0; i < arr.size(); i++) {
// If reachable > arr[i].first, there
// exist no path between arr[i].first
// and arr[i].second, hence continue
if (reachable > arr[i].first)
continue;
else {
// Update the reachable vertex
reachable = arr[i].second;
// Increment minEdges by 1
minEdges++;
}
}
// Return answer
return minEdges;
}
// Driver Code
int main()
{
vector<pair<int, int> > arr = {
{ 1, 8 }, { 2, 7 }, { 3, 5 }, { 4, 6 }, { 7, 9 }
};
int N = arr.size();
cout << findMinEdges(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.Arrays;
class GFG
{
// Comparator function to sort the
// given array of pairs in increasing
// order of second value of the pairs
// Function to find minimum number of edges
// to be removed such that there exist no
// path between each pair in the array arr[]
public static int findMinEdges(int[][] arr, int N)
{
// Stores the count of edges to be deleted
int minEdges = 0;
// Stores the smallest vertex reachable
// from the current vertex
int reachable = 0;
// Sort the array arr[] in increasing
// order of the second value of the pair
Arrays.sort(arr, (a, b) -> (a[1] - b[1]));
// Loop to iterate through array arr[]
for (int i = 0; i < arr.length; i++) {
// If reachable > arr[i][0], there
// exist no path between arr[i][0]
// and arr[i][1], hence continue
if (reachable > arr[i][0])
continue;
else {
// Update the reachable vertex
reachable = arr[i][1];
// Increment minEdges by 1
minEdges++;
}
}
// Return answer
return minEdges;
}
// Driver Code
public static void main(String args[]) {
int[][] arr = { { 1, 8 }, { 2, 7 }, { 3, 5 }, { 4, 6 }, { 7, 9 } };
int N = arr.length;
System.out.println(findMinEdges(arr, N));
}
}
// This code is contributed by _saurabh_jaiswal.
Python3
# Python 3 program for the above approach # Comparator function to sort the # given array of pairs in increasing # order of second value of the pairs # Function to find minimum number of edges # to be removed such that there exist no # path between each pair in the array arr[] def findMinEdges(arr, N): # Stores the count of edges to be deleted minEdges = 0 # Stores the smallest vertex reachable # from the current vertex reachable = 0 # Sort the array arr[] in increasing # order of the second value of the pair arr.sort() # Loop to iterate through array arr[] for i in range(len(arr)): # If reachable > arr[i].first, there # exist no path between arr[i].first # and arr[i].second, hence continue if (reachable > arr[i][0]): continue else: # Update the reachable vertex reachable = arr[i][1] # Increment minEdges by 1 minEdges += 1 # Return answer return minEdges+1 # Driver Code if __name__ == '__main__': arr = [[1, 8],[2, 7],[3, 5],[4, 6],[7, 9]] N = len(arr) print(findMinEdges(arr, N)) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
using System.Linq;
using System.Collections.Generic;
public class GFG {
// Comparator function to sort the
// given array of pairs in increasing
// order of second value of the pairs
// Function to find minimum number of edges
// to be removed such that there exist no
// path between each pair in the array []arr
public static int findMinEdges(List<List<int>> arr, int N) {
// Stores the count of edges to be deleted
int minEdges = 0;
// Stores the smallest vertex reachable
// from the current vertex
int reachable = 0;
// Sort the array []arr in increasing
// order of the second value of the pair
arr.Sort((a, b) => a[1] - b[1]);
// Loop to iterate through array []arr
for (int i = 0; i < arr.Count; i++) {
// If reachable > arr[i,0], there
// exist no path between arr[i,0]
// and arr[i,1], hence continue
if (reachable > arr[i][0])
continue;
else
{
// Update the reachable vertex
reachable = arr[i][1];
// Increment minEdges by 1
minEdges++;
}
}
// Return answer
return minEdges;
}
// Driver Code
public static void Main(String []args) {
int[,] arr = { { 1, 8 }, { 2, 7 }, { 3, 5 }, { 4, 6 }, { 7, 9 } };
List<List<int>> arr1 = new List<List<int>>();
for(int i = 0;i<arr.GetLength(0);i++){
List<int> arr2 = new List<int>();
arr2.Add(arr[i,0]);
arr2.Add(arr[i,1]);
arr1.Add(arr2);
}
int N = arr.GetLength(0);
Console.WriteLine(findMinEdges(arr1, N));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find minimum number of edges
// to be removed such that there exist no
// path between each pair in the array arr[]
function findMinEdges(arr,
N)
{
// Stores the count of edges to be deleted
let minEdges = 0;
// Stores the smallest vertex reachable
// from the current vertex
let reachable = 0;
// Sort the array arr[] in increasing
// order of the second value of the pair
arr.sort(function (a, b) { return a.second - b.second })
// Loop to iterate through array arr[]
for (let i = 0; i < arr.length; i++) {
// If reachable > arr[i].first, there
// exist no path between arr[i].first
// and arr[i].second, hence continue
if (reachable > arr[i].first)
continue;
else {
// Update the reachable vertex
reachable = arr[i].second;
// Increment minEdges by 1
minEdges++;
}
}
// Return answer
return minEdges;
}
// Driver Code
let arr = [{first: 1, second: 8},
{ first: 2, second: 7 },
{ first: 3, second: 5 },
{ first: 4, second: 6 },
{ first: 7, second: 9 }];
let N = arr.length;
document.write(findMinEdges(arr, N));
// This code is contributed by Potta Lokesh
</script>
Producción:
2
Complejidad de tiempo: O(M*log M)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por dharanendralv23 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA