Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!


Last Updated on February 24, 2022 by Ria Pathak

Concepts Used

Depth First Search

Difficulty Level


Problem Statement :

Given an undirected connected graph, you must find all the edges which when removed divide the graph.

See original problem statement here

Solution Approach :

Introduction :

A bridge is an edge, when removed, will disconnect the graph (or increase the number of connected components by 1). Idea is to check all edges if it is an edge or not.


Method 1 (Brute Force) :

We can iterate for all the edges and remove an edge ( u--v ) and check if the graph becomes disconnected, we can either use dfs or bfs for this. If graph becomes disconnected it means that the edge u,v is a bridge, store it somewhere and increment the bridge count. Now add the edge (u,v) back to the graph and repeat this process for all edges.

Method 2 (Efficient) :

One observation by referring certain websites to learn programming is that no edge that belong to a loop can be a bridge. So in a graph such as 1--2--3--1,removing any of the edge 1--2, 2--3 and 3--1 will not disconnect the graph. But for an undirected graph, the edge 1--2 implies 2--1, and this edge could still be a bridge, where the only loop it is in is 1--2--1. So, we should consider only those loops formed by a back edge. This is where the parent information you’ve passed in the function argument helps. It will help you to not use the loops such as 1--2--1.

Now to identify the back edge (or the loop), 1--2--3--1 we use the low and disc arrays. The array disc keeps track of the discovery time of each vertex. The low array helps to identify if there is a loop. The low array identifies the minimum discovery time (from disc array) that the current vertex can reach.


Algorithms :

bfs_Bridge() :

  1. Initialise the timer (timer=0).
  2. Iterate through vertex v, we will mark the vertex v as visited (visited[v]= true), and update discovery time and low (disc[v]= timer, low[v] = timer) .
  3. Iterate for all the adjacent vertices of v and for every adjacent vertex a, do following :
    • update the parent and distance as, parent[a] = v and
    • recursively call bfs_Brigdes(a)
    • update low[v]=min(low[u],low[v]),
    • if low[u]>disc[v], edge u,v is a brigde.
    • if a is not visited,
      and if parent[v] != a ,
    • update low[v] = min(low[v],disc[u])

Complexity Analysis:

The time complexity of the above method 2 is represented in the form of O(V+E), where V is the number of verices and E is the number of edges.


Leave a Reply

Your email address will not be published. Required fields are marked *