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 Searchvoid 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 removedint 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 Codeint 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 approachimport java.util.*;Â
class GFG{Â
// Function for Depth first Searchstatic 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 removedstatic 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 Codepublic 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 Searchdef 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 removeddef 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 CodeN = 6M = 7A = 1B = 6edges = [[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 approachusing System;using System.Collections.Generic;Â
public class GFG{Â
// Function for Depth first Searchstatic 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 removedstatic 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 Codepublic 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 Searchfunction 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 removedfunction 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 Codelet 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
3
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Info to that Topic: geeksforgeeks.org/minimum-edges-to-be-removed-from-given-undirected-graph-to-remove-any-existing-path-between-nodes-a-and-b/ […]
… [Trackback]
[…] Find More to that Topic: geeksforgeeks.org/minimum-edges-to-be-removed-from-given-undirected-graph-to-remove-any-existing-path-between-nodes-a-and-b/ […]
… [Trackback]
[…] Find More on on that Topic: geeksforgeeks.org/minimum-edges-to-be-removed-from-given-undirected-graph-to-remove-any-existing-path-between-nodes-a-and-b/ […]
… [Trackback]
[…] There you will find 18973 additional Information on that Topic: geeksforgeeks.org/minimum-edges-to-be-removed-from-given-undirected-graph-to-remove-any-existing-path-between-nodes-a-and-b/ […]
… [Trackback]
[…] Find More here on that Topic: geeksforgeeks.org/minimum-edges-to-be-removed-from-given-undirected-graph-to-remove-any-existing-path-between-nodes-a-and-b/ […]
… [Trackback]
[…] Find More here to that Topic: geeksforgeeks.org/minimum-edges-to-be-removed-from-given-undirected-graph-to-remove-any-existing-path-between-nodes-a-and-b/ […]