Check if the given edge is a bridge in the graph

Problem Statement:

You are given a graph and an edge, you need to check if that edge is a bridge.

Example

Solution

An edge is called a bridge, if you remove that edge, then it will disconnect the graph.

In the above example, the edge between the nodes “3” and “4” is a bridge.

We can solve this problem by using DFS method.

Calculate connected component using DFS for the graph

Remove the edge

Calculate the connected component using DFS again. If the count increases then given edge is a bridge.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 
#include <list> 

using namespace std;

class Graph
{

private:
   int V; 
   list<int> *adj; // to hold adjacency list
   void helper(int v, bool visited[]); // helper function for check_if_connected
public:
   Graph(int V); // Constructor
   void add_edge(int v, int w); // to add an edge to graph
   int check_bridge(int u, int v ); // returns true if there is a cycle in this graph
};

Graph::Graph(int V)
{
   // get the total number of nodes
   this->V = V;

   // initialize adjacency list for that number of nodes
   adj = new list<int>[V];
}

void Graph::add_edge(int v, int w)
{
   // add the edge to adjacency list
   adj[v].push_back(w); 
   adj[w].push_back(v); 
}


void Graph::helper(int v, bool visited[])
{
      visited[v] = true;
      for(auto i = adj[v].begin(); i != adj[v].end(); i++)
      {
         int adjVertex = *i;

         if ( !visited[adjVertex]){
             helper(adjVertex, visited);
         }
      }
}

int Graph::check_bridge(int u, int v)
{
    bool *visited = new bool[V];
    int count  = 0;

    // remove the edge from undirected graph
    adj[u].remove(v);
    adj[v].remove(u);

   for(int i = 0; i < V; i++)
   {
      visited[i] = false;
   }

    for (int v = 0; v < V; v++) 
    {
        if (visited[v] == false) {
            helper(v, visited);
            count ++;
        }
    }
   return count;
}


int main()
{

   Graph g(4);
   g.add_edge(0, 1);
   g.add_edge(1, 2);
   g.add_edge(2, 3);

   if(g.check_bridge(1, 2) > 1){
      cout<<"Given edges are bridge"<<endl;
   } else {
      cout<<"Given edges are not bridge"<<endl;
}
   return 0;
}

Output:

Given edges are bridge