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.
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)
{
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 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)

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: