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

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

You can also try this code with Online C++ Compiler

Run Code

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: 

• Detect cycle in an undirected graph
• Shortest Path In Binary Matrix
• Binary Array Sorting

To learn more about graphs, refer to this link. 

Until then, Keep Learning and Keep Coding.