Minimum edges to be removed from given undirected graph to remove any existing path between nodes A and B

0 0 7 minutes read

Given two integers N and M denoting the number of vertices and edges in the graph and array edges[][] of size M, denoting an edge between edges[i][0] and edges[i][1], the task is to find the minimum edges directly connected with node B that must be removed such that there exist no path between vertex A and B.

Examples:

Input: N = 4, A = 3, B = 2, edges[][] = {{3, 1}, {3, 4}, {1, 2}, {4, 2}}
Output: 2
Explanation: The edges at index 2 and 3 i.e., {1, 2} and {4, 2} must be removed as they both are in the path from vertex A to vertex B.

Input: N = 6, A = 1, B = 6, edges[][] = {{1, 2}, {1, 6}, {2, 6}, {1, 4}, {4, 6}, {4, 3}, {2, 4}}
Output: 3

Approach: The given problem can be solved using a Depth-first search algorithm. It can be observed that all the edges associated with the ending vertex B and exist in any path from starting node A and ending at node B must be removed. Hence, perform a dfs starting from node A and maintain all the visited vertices from it. Follow the steps below to solve the problem:

Create an adjacency matrix g[][] which stores the edges between two nodes.
Initialize an array v[], to mark the node which can be reached from node A.
Create a variable cnt, which stores the count of nodes needed to be removed. Initially, cnt = 0.
Iterate through all the nodes and if it is reachable from A and is directly connected with B, increment the value of cnt.
The value stored in cnt is the required answer.

Below is the implementation of the above approach:

C++

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

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

Python3

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

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

Javascript

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

Output

Time Complexity: O(N)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!