Last Updated: 20 Nov, 2020

Bridges In A Graph

Moderate
Asked in companies
IBMGoogleArcesium

Problem statement

Given an undirected graph of V vertices and E edges. Your task is to find all the bridges in the given undirected graph. A bridge in any graph is defined as an edge which, when removed, makes the graph disconnected (or more precisely, increases the number of connected components in the graph).

For Example :

If the given graph is :

graph

Then the edge between 0 and 4 is the bridge because if the edge between 0 and 4 is removed, then there will be no path left to reach from 0 to 4.and makes the graph disconnected, and increases the number of connected components.

Note :

There are no self-loops(an edge connecting the vertex to itself) in the given graph.

There are no parallel edges i.e no two vertices are directly connected by more than 1 edge.
Input Format :
The first line of input contains an integer T, the number of test cases.

The first line of each test case contains two single space-separated integers V, and E.

From the second line onwards of each test case, the next 'E' lines will denote the edges of the graph where every edge is defined by two single space-separated integers 'a' and 'b', which signifies an edge between vertex 'a’ and vertex 'b'.
Output Format :
For each test case, 
In the first line, print a single integer C denoting the count of bridges in the given graph.

From the second line onwards of each test case, Print C lines, each line contains one edge i.e two space-separated integers a and b, where C denotes the number of bridges in the given graph.
Note :
In the output format
Each pair of vertices of a bridge will be sorted i.e the first value should be less than or equals to the second value.

The list of bridge edges will be sorted in non-decreasing order of their first value. In case if two pairs have the same first value, the pair with a smaller second value will come first.

You do not need to print or sort anything, it has already been taken care of. Just implement the given function. 
Constraints :
1 <= T <= 50
1 <= V <= 10 ^ 3
V-1 <= E <= 3 * 10^3
0 <= a, b < V

Time Limit: 1 sec

Approaches

01 Approach

The brute force approach to find all the bridges in a given graph is to check for every edge if it is a bridge or not, by first not considering current edge is not in given graph and then checking if the vertices that it was connecting are still connected or not, using DFS(DepthFirst Search). Given below is an algorithm that will find all bridges in a graph.

 

Algorithm :

  1. Initialise a visited array with false
  2. For each edge in the graph:
    1. Mark all the vertices as not visited
    2. Define and call the helper function, isBridge(graph visited, u, v, u)  to check whether the current edge is a bridge or not where the graph is the given graph, u and v are the vertices of the current edge and visited is the boolean array. This will basically check whether there is a path between u and v if we ignore the direct edge between u and v.
      1. Store the current edge in the answer if the current edge is a bridge.

 

Boolean isBridge(graph, visited, currentVertex, a, b) {

  1. Mark the currentVertex node as visited.
  2. Iterate on all the adjacent vertices to currentVertex node
    1. Skip the adjacent vertice if it is already visited or (currentVertex is u and adjacent is v).
    2. If the adjacent vertex is not visited:
      1. If the adjacent vertex is v and not the adjacent vertice of u then return false.
      2. Else recursively call the function for unvisited vertices, If the recursive function returns false, return false.
  3. The current edge(u,v) is a bridge, Return true.

02 Approach

The idea of this approach is to do DFS traversal of the given graph as also explained in this article. 

  • In a DFS tree, an edge (u, v) (u is the parent of v in a DFS tree) is a bridge if and only if
    • There does not exist any other alternative to reach v from u.
    • Or none of the vertices v and its descendants in the DFS traversal tree has a back-edge to vertex u or any of its ancestors. The reason is that each back edge gives us a cycle, and no edge that is a member of a cycle can be a bridge.
  • Now to check this we will be maintaining two arrays
    • in[] - this stores the time when the vertex is first visited.
    • low[] - for every vertex u it stores the discovery time of the earliest visited vertex to which the vertex u or any of its descendants which have a back edge. Thus, low[u] is the minimum of three values,
      • in[u]: the discovery time of vertex v.
      • in[p]: where p is an ancestor of u in the dfs tree and have an edge with p, i.e there is a back edge between p and u.
      • low[v]: where there is a tree edge between u and v. This means that v is a vertex directly connected to u with an edge and v is not the parent node of u in the dfs tree.

 

  • Initially, we will initialize low[] to -1. We will also initialize one variable timer = 0 to keep track of current discovery time.
  • Now, there is a back edge from v or one of its descendants to ancestors of u (u is the parent of v) if and only if low[v]≤ tin[u]. This is due to the fact that if there is a back edge then the value of low[v] must be lesser than tin[u]. If low[v]=tin[u] then the back edge comes directly from v to u. Thus, the edge (u,v) in the DFS tree is a bridge if and only if low[v]>tin[u].