AlgoViz
HomeGraphs

Bridges in graph

Hard

Tarjan: compare discovery and low-link times

Problem

Find all bridges (edges whose removal disconnects the graph) using Tarjan's algorithm.

In simple words

An edge is a bridge if the far side can't reach back around any other way.

The idea

During DFS record when each vertex was discovered and the earliest discovery time reachable from its subtree. An edge to a child whose low-link exceeds the parent's discovery time is a bridge, because nothing below can reach back above it.

The trick

  • Bridge condition: low[child] > disc[parent].
  • Skip the edge back to the parent, but not other edges to visited vertices.
  • O(V + E) in a single DFS.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

0
0

Step 1 of 2. Here's the example — graph Values: 0.

1/2
Optimal
timeO(V+E)spaceO(V)
1DFS tracking discovery time and low-link2edge (u,v) is a bridge if low[v] > disc[u]

Input

array
[0]

Output

answer
—

Check yourself

2 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:
graph
Output:
list of bridges

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.