If the given graph is :
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.
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.
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'.
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.
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.
1 <= T <= 50
1 <= V <= 10 ^ 3
V-1 <= E <= 3 * 10^3
0 <= a, b < V
Time Limit: 1 sec
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.
Boolean isBridge(graph, visited, currentVertex, a, b) {
The idea of this approach is to do DFS traversal of the given graph as also explained in this article.