Last Updated on February 24, 2022 by Ria Pathak

Concepts Used

Depth First Search

Difficulty Level

Hard

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.

IMAGE HERE

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.

IMAGE HERE!!! (EXAMPLE)

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.

Solutions: