Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Some Examples
2.
DFS Approach
2.1.
Steps of Algorithm
3.
Implementation in C++
3.1.
Complexity Analysis
4.
Frequently asked questions
5.
Key takeaways
Last Updated: Mar 27, 2024

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

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

This blog will discuss the solution to the problem of finding minimum edges connected to node B to be removed from undirected graph to remove any existing path between nodes A and B. 

Problem Statement

Here we are given N, M, A, and B, where N denotes the number of vertices, M denotes the number of edges in the graph, and A and B denote the nodes. We are also given an array edges[] [] which is of size M, here edge is represented by edges[i] [0] and edges[i][1]. Our task is to find the minimum edges connected to node B, which need to be removed such that no path exists between nodes A and B.

Some Examples

Example 1:

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

Explanation:
Indexes 3, 4  from the matrix edges[][] must be removed because they are in the path of A and B.

 

Example 2:

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

Explanation:
Indexes 0, 5, 6  from the matrix edges[][] must be removed because they are in the path of A and B.

DFS Approach

To find the minimum edges connected to node B to be removed from undirected graph to remove any existing path between nodes A and B. We will solve this problem using a depth-first search. As we can see from the problem, we need to remove edges that are connected to node B so that there remains no existing path from A to B. 

If A=1, B=3 and there are two edges {1, 2}, {2, 3} then if we remove any one from these two edges, this path would become non-existent.

Steps of Algorithm

  1. We will first create an adjacency matrix graph[] [], and this matrix will store the edge between two nodes.
  2. We will initialize a visited array to mark the visited node. 
  3. Now, we will create a variable named cnt to store the count of edges needed to be removed from the graph.
  4. After that, we will iterate through all nodes of the graph, and we will check if there exists a path from the current node to A. If it is also directly connected to B, we will increment the cnt. 
  5. After the whole iteration is over, then we will return cnt.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Implementation in C++

// C++ code to find the minimum edges connected to node B to be removed from undirected graph to remove any existing path between nodes A and B
#include <bits/stdc++.h>
using namespace std;

// function to do dfs on undirected graph
void dfs(int s, vector<vector<int>> graph,
        vector<int> &visited)
{
    for (auto i : graph[s])
    {

        // if the current node is not visited then visit it
        if (!visited[i])
        {
            visited[i] = 1;

            // call dfs from this node
            dfs(i, graph, visited);
        }
    }
}

// function to find the minimum edges connected to node B to be removed from undirected graph to remove any existing path between nodes A and B
int removeEdges(int n, int m, int a, int b,
                vector<vector<int>> edges)
{
    // create an adjaceny matrix
    vector<vector<int>> graph(n + 1, vector<int>());
    for (int i = 0; i < m; i++)
    {
        graph[edges[i][0]].push_back(edges[i][1]);
        graph[edges[i][1]].push_back(edges[i][0]);
    }

    // visited array
    vector<int> visited(n+1, 0);
    visited[a] = 1;

    // to call dfs
    dfs(a, graph, visited);

    // to store the final count
    int cnt = 0;

    for (int i = 0; i < n; i++)
    {

        // if the current node can't be visited from node A
        if (visited[i] == 0)
            continue;

        for (int j = 0; j < graph[i].size(); j++)
        {

            // if a path exist from current node to both
            // node a and node b then increment the count
            if (graph[i][j] == b)
            {
                cnt++;
            }
        }
    }

    // return the answer
    return cnt;
}

// Driver Code
int main()
{
    int N = 6, M = 6, A = 3, B = 6;
    vector<vector<int>> edges{
        {5, 2}, {3, 4}, {2, 3}, {3, 6}, {4, 6}, {5, 6}};

    cout << removeEdges(N, M, A, B, edges);

    return 0;
}

 

Output:

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

 

Complexity Analysis

Time Complexity: O(N)

Space Complexity: O(N)

Frequently asked questions

Q1. What are the nodes of the graph?

Ans: The nodes are the fundamental units by which a graph is formed. Nodes are also termed as vertices of the graph.

 

Q2. What is the purpose of making a visited array?

Ans: The visited array is made to track which nodes are visited and which nodes are not visited, and the visited array can store only two values. If the node is visited, it will store true. Otherwise, it will store false.

 

Q3. What is an undirected graph?

Ans: An undirected graph is a graph where we can travel in both directions. For example, if there is node A and another node B in the graph, then we can go from A->B, and we can also go from B->A.

Key takeaways

In this article, we have discussed the problem to count the minimum edges connected to node B to be removed from undirected graph to remove any existing path between nodes A and B. We have discussed its approach based on the depth-first approach, and we have also discussed the time and space complexities of this approach.

Recommended Problems: 

To learn more about graphs, refer to this link. 

Until then, Keep Learning and Keep Coding.


Previous article
Shortest path in a Matrix from top-left to bottom right-corner with neighbours exceeding at most K
Next article
Minimum Vertex Cover Size of a Graph Using Binary Search
Live masterclass