Biconnected Component Problems
1 Biconnected Component LeetCode problems · Browse tasks by difficulty and choose your next practice problem.
Learn the coding interview patterns behind these problems.
Find the connections a network cannot lose
In an undirected graph, an articulation vertex increases the number of connected components when removed. A bridge does the same when one edge is removed. Biconnected components group edges into blocks that have no articulation vertex within the block. Critical Connections in a Network asks for bridges, so distinguish the edge test from the vertex test.
When to use it
Use a depth-first search with discovery times and low-link values when a problem asks which single failure disconnects an undirected network. A child's low value records the earliest discovery time reachable through its subtree and a back edge.
Worked example
Edges: A–B, B–C, C–A, C–D.
- Visit A, B, C, D in that order. The back edge C–A lets C's subtree reach A without using B–C.
- D has no back edge. Its low value stays greater than C's discovery time, so C–D is a bridge.
- Removing C separates D from A and B. Removing any single triangle edge leaves an alternative route.
C is an articulation vertex; C–D is the only bridge. The triangle and C–D form separate blocks.
Time and space
Bridge and articulation detection takes O(V + E) time and O(V) auxiliary state with adjacency lists. Extracting biconnected blocks with the standard edge-stack method also requires up to O(E) stack space, excluding the graph and returned blocks. Deep graphs may need an explicit DFS stack to avoid recursion limits.
Mistakes to check
- For a DFS tree edge parent→child, the bridge condition is low[child] > discovery[parent]. The non-root articulation condition uses >= instead.
- A DFS root is an articulation vertex only when it has more than one DFS child. Start a search in every disconnected component.
- If parallel edges are allowed, skip the incoming edge by its ID, not every edge to the parent vertex.
Further reading: Boost Graph: biconnected components and articulation points
Guide reviewed .