Bridges in Graph

Given an undirected graph with V vertices (0 .. V-1) and edges edges (no self-loops or duplicate edges), return all bridges — edges whose removal increases the number of connected components. Return each bridge as [min(u,v), max(u,v)], and return the list sorted.

Hints

· Stuck? Reveal one nudge at a time.

A bridge is an edge that lies on no cycle — removing it disconnects part of the graph.

DFS tracking disc[u] (discovery time) and low[u] (earliest reachable ancestor).

A tree edge u-v is a bridge iff low[v] > disc[u].

Common doubts

v's subtree has no back edge reaching u or above, so the edge (u,v) is the only connection holding that subtree on — a bridge.

A back edge climbs to an already-visited ancestor w; its discovery time is the level you can reach, so use disc[w].

With multi-edges, a second parallel edge to the parent forms a cycle and must be counted; skipping just one preserves that.

Interview follow-ups

· What an interviewer asks next.

Use low[v] ≥ disc[u] (non-strict) for non-root vertices, and handle the root by child count.

A graph is 2-edge-connected iff it has no bridges.

Fun facts

Bridges are exactly the edges not contained in any cycle — the 'cut edges' of the graph.
Tarjan's 1974 bridge algorithm shares its low-link engine with SCCs and articulation points.

Asked at

GoogleAmazonMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: V = 4, edges = [[0,1],[1,2],[2,0],[2,3]]
Output: [[2,3]]
The triangle 0-1-2 has no bridge; 2-3 is the only link to vertex 3.

Example 2

Input: V = 4, edges = [[0,1],[1,2],[2,3],[3,0]]
Output: []
A single cycle has no bridges.

Constraints

- 1 <= V <= 10^5 - 0 <= edges.length <= 10^5 - no self-loops or duplicate edges

A bridge is an edge that no cycle covers — remove it and the graph falls apart a little more. Tarjan's algorithm finds all of them in one DFS using two timestamps per vertex:

disc[u] — when u was first discovered.
low[u] — the smallest discovery time reachable from u's subtree via tree edges plus one back edge.

For a tree edge u → v, the edge is a bridge exactly when low[v] > disc[u]: the subtree rooted at v has no back edge climbing to u or above, so (u, v) is the only link holding it on. Update low[u] from children's low (tree edges) and from disc[w] on back edges. Skip the single edge back to the parent. O(V + E).

The brute force removes each edge and recounts components (O(E · (V + E))) — correct but far slower.

Prerequisites

Before you start

· Concepts used directly in the solution.

disc & low. discovery time and earliest reachable ancestor.

Bridge condition. low[v] > disc[u] for a tree edge.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“What's a bridge?”

An edge whose removal increases the number of components.

“Output format?”

Each bridge as [min, max], list sorted.

The ideal opening — say it like this

I DFS tracking discovery times and low-links; a tree edge u-v is a bridge when low[v] > disc[u].

That means v's subtree has no back edge climbing above u, so the edge isn't on any cycle.

Understand the problem

Worked example — V = 4, edges [[0,1],[1,2],[2,0],[2,3]]

0-1-2 form a cycle -> none are bridges (each has a back edge)
2-3 is the only link to 3 -> bridge
answer = [[2,3]]

Key observations

1Aha

Bridges are edges on no cycle

A back edge covering an edge disqualifies it.

2Aha

low[v] > disc[u] ⇒ bridge

v's subtree can't climb above u.

3Aha

Single DFS, O(V+E)

disc and low computed in one pass.

Brute force vs optimal

	Remove each edge	Tarjan (disc/low)
Idea	recount components without it	one DFS with low-links
Time	O(E·(V+E))	O(V+E)
Bridges	component count increases	low[v] > disc[u]

Both find the same bridges. Full code is in the Approaches selector below.

Summary

Key takeaway

A bridge is an edge on no cycle. Tarjan's DFS finds them via low-links: a tree edge u-v is a bridge iff low[v] > disc[u]. O(V+E).

dfs(u, parent): for child v: if low[v] > disc[u] -> bridge (u,v)