Bridges In A Graph

Moderate
0/80
Average time to solve is 25m
76 upvotes
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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
5 4
0 1
3 1
1 2
3 4
3 3
0 1
1 2
2 0
Sample Output 1 :
4
0 1
1 2    
1 3
3 4
0
Explanation for Sample Input 1 :
For the first test case, the graph will be represented as

graph

There are four bridges((0-1),(1-2),(1-3),(3-4)) in the above-given graph denoted by red lines.
For the second test case, there is no bridge present in the given graph.
Sample Input 2 :
1
6 7
1 2
1 0
0 2
0 4
5 4
5 3
3 4
Sample Output 2 :
1
0 4
Explanation for Sample Input 2 :
For the first test case, the graph will be represented as

graph

There is only one bridge((0-4)) in the above-given graph denoted by red lines.
Hint

Think of brute force by not considering each edge one at a time and checking if the edge is bridge or not.

Approaches (2)
Brute Force

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.
Time Complexity

O(E * (V + E)), where V is the number of vertices and E is the number of edges in the graph.

 

In the worst case for each edge present in graph O(E), we will traverse the whole graph O(V+E), Hence the overall complexity will be O(E * (V + E)).

Space Complexity

O(V), where V is the number of vertices in the graph.

 

In the worst case, extra space is required to store visited vertices O(V) and also an extra space is used by recursion function call stack O(V). 

Code Solution
(100% EXP penalty)
Bridges In A Graph
Full screen
Console