Los bordes mínimos que se eliminarán del gráfico no dirigido dado para eliminar cualquier ruta existente entre los Nodes A y B

Dados dos números enteros N y M que denotan el número de vértices y aristas en el gráfico y la array edge [][] de tamaño M , que denota una arista entre aristas[i][0] y aristas[i][1] , la tarea es para encontrar los bordes mínimos conectados directamente con el Node B que deben eliminarse de modo que no exista un camino entre el vértice A y B.

Ejemplos:

Entrada: N = 4, A = 3, B = 2, bordes[][] = {{3, 1}, {3, 4}, {1, 2}, {4, 2}}
Salida:  2
Explicación: Los bordes en el índice 2 y 3, es decir, {1, 2} y {4, 2} deben eliminarse ya que ambos están en la ruta del vértice A al vértice B.

Entrada: N = 6, A = 1, B = 6, bordes[][] = {{1, 2}, {1, 6}, {2, 6}, {1, 4}, {4, 6} , {4, 3}, {2, 4}}
Salida: 3

Enfoque: el problema dado se puede resolver utilizando un algoritmo de búsqueda primero en profundidad . Se puede observar que todas las aristas asociadas al vértice final B y existentes en cualquier camino desde el Node inicial A y finalizando en el Node B deben ser removidas. Por lo tanto, realice un dfscomenzando desde el Node A y manteniendo todos los vértices visitados desde él. Siga los pasos a continuación para resolver el problema:

• Cree una array de adyacencia g[][] que almacene los bordes entre dos Nodes.
• Inicialice una array v[] para marcar el Node al que se puede acceder desde el Node A.
• Cree una variable cnt , que almacene la cantidad de Nodes necesarios para eliminar. Inicialmente, cnt = 0 .
• Iterar a través de todos los Nodes y si es accesible desde A y está directamente conectado con B , incrementar el valor de cnt .
• El valor almacenado en cnt es la respuesta requerida.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function for Depth first Search
void dfs(int s, vector<vector<int> > g,
         vector<int>& v)
{
    for (auto i : g[s]) {
 
        // If current vertex is
        // not visited yet
        if (!v[i]) {
            v[i] = 1;
 
            // Recursive call for
            // dfs function
            dfs(i, g, v);
        }
    }
}
 
// Function to find the out the minimum
// number of edges that must be removed
int deleteEdges(int n, int m, int a, int b,
                vector<vector<int> > edges)
{
    // Creating Adjacency Matrix
    vector<vector<int> > g(n, vector<int>());
    for (int i = 0; i < m; i++) {
        g[edges[i][0] - 1].push_back(edges[i][1] - 1);
        g[edges[i][1] - 1].push_back(edges[i][0] - 1);
    }
 
    // Vector for marking visited
    vector<int> v(n, 0);
    v[a - 1] = 1;
 
    // Calling dfs function
    dfs(a - 1, g, v);
 
    // Stores the final count
    int cnt = 0;
 
    for (int i = 0; i < n; i++) {
 
        // If current node can not
        // be visited from node A
        if (v[i] == 0)
            continue;
        for (int j = 0; j < g[i].size(); j++) {
 
            // If a node between current
            // node and node b exist
            if (g[i][j] == b - 1) {
                cnt++;
            }
        }
    }
 
    // Return Answer
    return cnt;
}
 
// Driver Code
int main()
{
    int N = 6;
    int M = 7;
    int A = 1;
    int B = 6;
    vector<vector<int> > edges{
        { 1, 2 }, { 5, 2 }, { 2, 4 },
        { 2, 3 }, { 3, 6 }, { 4, 6 }, { 5, 6 }
    };
 
    cout << deleteEdges(N, M, A, B, edges);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function for Depth first Search
static void dfs(int s, Vector<Integer> [] g,
         int[] v)
{
    for (int i : g[s]) {
 
        // If current vertex is
        // not visited yet
        if (v[i] == 0) {
            v[i] = 1;
 
            // Recursive call for
            // dfs function
            dfs(i, g, v);
        }
    }
}
 
// Function to find the out the minimum
// number of edges that must be removed
static int deleteEdges(int n, int m, int a, int b,
                int[][] edges)
{
   
    // Creating Adjacency Matrix
    Vector<Integer> []g = new Vector[n];
    for (int i = 0; i < g.length; i++)
        g[i] = new Vector<Integer>();
    for (int i = 0; i < m; i++) {
        g[edges[i][0] - 1].add(edges[i][1] - 1);
        g[edges[i][1] - 1].add(edges[i][0] - 1);
    }
 
    // Vector for marking visited
    int []v = new int[n];
    v[a - 1] = 1;
 
    // Calling dfs function
    dfs(a - 1, g, v);
 
    // Stores the final count
    int cnt = 0;
 
    for (int i = 0; i < n; i++) {
 
        // If current node can not
        // be visited from node A
        if (v[i] == 0)
            continue;
        for (int j = 0; j < g[i].size(); j++) {
 
            // If a node between current
            // node and node b exist
            if (g[i].get(j) == b - 1) {
                cnt++;
            }
        }
    }
 
    // Return Answer
    return cnt;
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 6;
    int M = 7;
    int A = 1;
    int B = 6;
    int[][] edges ={
        { 1, 2 }, { 5, 2 }, { 2, 4 },
        { 2, 3 }, { 3, 6 }, { 4, 6 }, { 5, 6 }
    };
 
    System.out.print(deleteEdges(N, M, A, B, edges));
 
}
}
 
// This code is contributed by 29AjayKumar

# Python program for the above approach
 
# Function for Depth first Search
def dfs(s, g, v):
    for i in g[s]:
 
        # If current vertex is
        # not visited yet
        if not v[i]:
            v[i] = 1
 
            # Recursive call for
            # dfs function
            dfs(i, g, v)
 
# Function to find the out the minimum
# number of edges that must be removed
def deleteEdges(n, m, a, b, edges):
 
    # Creating Adjacency Matrix
    g = [0] * m
    for i in range(len(g)):
        g[i] = []
 
    for i in range(m):
        g[edges[i][0] - 1].append(edges[i][1] - 1)
        g[edges[i][1] - 1].append(edges[i][0] - 1)
 
    # Vector for marking visited
    v = [0] * n
    v[a - 1] = 1
 
    # Calling dfs function
    dfs(a - 1, g, v)
 
    # Stores the final count
    cnt = 0
 
    for i in range(n):
 
        # If current node can not
        # be visited from node A
        if (v[i] == 0):
            continue
 
        for j in range(len(g[i])):
 
            # If a node between current
            # node and node b exist
            if (g[i][j] == b - 1):
                cnt += 1
 
    # Return Answer
    return cnt
 
# Driver Code
N = 6
M = 7
A = 1
B = 6
edges = [[1, 2], [5, 2], [2, 4],
         [2, 3], [3, 6], [4, 6],
         [5, 6]]
 
print(deleteEdges(N, M, A, B, edges))
 
# This code is contributed by gfgking

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG{
 
// Function for Depth first Search
static void dfs(int s, List<int> [] g,
         int[] v)
{
    foreach (int i in g[s]) {
 
        // If current vertex is
        // not visited yet
        if (v[i] == 0) {
            v[i] = 1;
 
            // Recursive call for
            // dfs function
            dfs(i, g, v);
        }
    }
}
 
// Function to find the out the minimum
// number of edges that must be removed
static int deleteEdges(int n, int m, int a, int b,
                int[,] edges)
{
   
    // Creating Adjacency Matrix
    List<int> []g = new List<int>[n];
    for (int i = 0; i < g.Length; i++)
        g[i] = new List<int>();
    for (int i = 0; i < m; i++) {
        g[edges[i,0] - 1].Add(edges[i,1] - 1);
        g[edges[i,1] - 1].Add(edges[i,0] - 1);
    }
 
    // List for marking visited
    int []v = new int[n];
    v[a - 1] = 1;
 
    // Calling dfs function
    dfs(a - 1, g, v);
 
    // Stores the readonly count
    int cnt = 0;
 
    for (int i = 0; i < n; i++) {
 
        // If current node can not
        // be visited from node A
        if (v[i] == 0)
            continue;
        for (int j = 0; j < g[i].Count; j++) {
 
            // If a node between current
            // node and node b exist
            if (g[i][j] == b - 1) {
                cnt++;
            }
        }
    }
 
    // Return Answer
    return cnt;
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 6;
    int M = 7;
    int A = 1;
    int B = 6;
    int[,] edges ={
        { 1, 2 }, { 5, 2 }, { 2, 4 },
        { 2, 3 }, { 3, 6 }, { 4, 6 }, { 5, 6 }
    };
 
    Console.Write(deleteEdges(N, M, A, B, edges));
}
}
 
// This code is contributed by shikhasingrajput

<script>
 
// JavaScript program for the above approach
 
// Function for Depth first Search
function dfs(s, g, v)
{
    for(let i of g[s])
    {
         
        // If current vertex is
        // not visited yet
        if (!v[i])
        {
            v[i] = 1;
 
            // Recursive call for
            // dfs function
            dfs(i, g, v);
        }
    }
}
 
// Function to find the out the minimum
// number of edges that must be removed
function deleteEdges(n, m, a, b, edges)
{
     
    // Creating Adjacency Matrix
    let g = new Array(m);
    for(let i = 0; i < g.length; i++)
    {
        g[i] = [];
    }
 
    for(let i = 0; i < m; i++)
    {
        g[edges[i][0] - 1].push(edges[i][1] - 1);
        g[edges[i][1] - 1].push(edges[i][0] - 1);
    }
 
    // Vector for marking visited
    let v = new Array(n).fill(0)
    v[a - 1] = 1;
 
    // Calling dfs function
    dfs(a - 1, g, v);
 
    // Stores the final count
    let cnt = 0;
 
    for(let i = 0; i < n; i++)
    {
         
        // If current node can not
        // be visited from node A
        if (v[i] == 0)
            continue;
             
        for(let j = 0; j < g[i].length; j++)
        {
             
            // If a node between current
            // node and node b exist
            if (g[i][j] == b - 1)
            {
                cnt++;
            }
        }
    }
     
    // Return Answer
    return cnt;
}
 
// Driver Code
let N = 6;
let M = 7;
let A = 1;
let B = 6;
let edges = [ [ 1, 2 ], [ 5, 2 ], [ 2, 4 ],
              [ 2, 3 ], [ 3, 6 ], [ 4, 6 ],
              [ 5, 6 ] ];
 
document.write(deleteEdges(N, M, A, B, edges));
 
// This code is contributed by Potta Lokesh
 
</script>

3

Complejidad temporal: O(N)
Espacio auxiliar: O(N)