Bridges in graph - DSA Practice

Given an undirected connected Graph with V vertices (Numbered from 0 to V-1) and E edges. An edge is represented [a_i, b_i] denoting that there is an edge from vertex a_i to b_i . An edge is called a bridge if its removal makes some vertex unable to reach another vertex.

Return all bridges in the graph in any order.

Example 1:

Input: V = 4, E = [ [0,1],[1,2],[2,0],[1,3] ]

Output: [ [1, 3] ]

Explanation: The edge [1, 3] is the critical edge because if we remove the edge the graph will be divided into 2 components.

Example 2:

Input: V = 3, E = [[0,1],[1,2],[2,0]]

Result: []

Explanation: There no bridges in the graph.

Now Your Turn!

Pick the correct output for the given input

Input: V = 2, E = [[0,1]]

[[0,1]][ ]

Still unsure what the problem is asking ?

Let’s go through a few more examples, step by step, to make it clearer.

Constraints:

2 <= V, E <= 10⁴
0 <= a_i, b_i <= V - 1

143. Bridges in graph

Example 1:

Example 2:

Now Your Turn!

Constraints:

Hints

Frequently Occurring Doubts

Interview Follow-up Questions

Fun Facts

Example 1:

Example 2:

Now Your Turn!

Constraints:

Hints

Hint 1

Hint 2

Frequently Occurring Doubts

Why not use simple DFS to find bridges?

Why use low[] instead of just tracking parent-child relationships?

Interview Follow-up Questions

What if the graph had duplicate edges?

Can we modify the algorithm to find articulation points (cut vertices)?

Fun Facts

Fun Fact 1

Fun Fact 2