Biconnected Component Coding Problems: 2 Questions with Solutions

How biconnected component works, step by step

1. Tarjan's DFS stamps each node with disc, the time it is reached, and low, the smallest disc its subtree can reach through one back edge. Start at A: disc = low = 1.
2. A → B is a tree edge: disc[B] = low[B] = 2. Until a back edge says otherwise, a node's low is its own disc.
3. B → C is a tree edge: disc[C] = 3. Its neighbour A is an ancestor already discovered, so C–A is a back edge and low[C] drops to 1: C's subtree can climb above B.
4. C → D is a tree edge: disc[D] = low[D] = 4. Its neighbours E and F are still undiscovered, so the search goes on to E first.
5. D → E is a tree edge: disc[E] = low[E] = 5. Its one undiscovered neighbour, F, is next.
6. E → F is a tree edge: disc[F] = 6. Its neighbour D is an ancestor already discovered, so F–D is a back edge and low[F] drops to 4: F's subtree can climb above E.
7. F returns to E: low[E] = min(5, low[F] = 4) = 4. low[F] = 4 < disc[E] = 5: F's subtree has a back edge to above E, so it stays connected without E.
8. E returns to D: low[D] = min(4, low[E] = 4) = 4. low[E] = 4 ≥ disc[D] = 4: nothing below D climbs above it, so removing D cuts E's side off. D is a cut vertex.
9. D returns to C: low[C] = min(1, low[D] = 4) = 1. low[D] = 4 ≥ disc[C] = 3: nothing below C climbs above it, so removing C cuts D's side off. C is a cut vertex, and since 4 > 3, C–D is a bridge.
10. C returns to B: low[B] = min(2, low[C] = 1) = 1. low[C] = 1 < disc[B] = 2: C's subtree has a back edge to above B, so it stays connected without B.
11. B returns to A, the root, which is a cut vertex only with two or more DFS children; A has only one. Result: cut vertices C and D, bridge C–D, components {A, B, C}, {C, D} and {D, E, F}, from one DFS: O(V + E).

Biconnected Component study plan

All 2 Biconnected Component problems (2 hard) over 2 days, about 1 h 55 min in all — the pattern first, then easiest to hardest. Then move on to Dynamic Programming.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve this problem.

• Critical Connections in a Network Hard

Day 2

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

• Minimum Number of Days to Disconnect Island Hard

Next topic: Dynamic Programming

Biconnected Component: the essentials

When to reach for it

"Which connections are critical", "which single server, road or cell disconnects the rest if it fails", "the fewest removals that split the network" — single points of failure in an undirected graph. Removing each edge in turn and re-testing connectivity costs O(E × (V + E)); one depth-first search with low-link values finds every bridge and articulation point in O(V + E).

The pattern

Number the nodes in the order a Depth-First Search discovers them (disc); low[u] is the smallest number u's subtree reaches by tree edges down, then one other edge up. After child v returns, u–v is a bridge if low[v] > disc[u], and u an articulation point if low[v] >= disc[u]. Non-tree edges join a node to an ancestor or descendant, so depth can serve as disc.

def critical_connections(adj):          # connected, undirected, no repeated edges
    disc, low, out = [-1] * len(adj), [0] * len(adj), []
    def dfs(u, parent, depth):
        disc[u] = low[u] = depth
        for v in adj[u]:
            if disc[v] == -1:
                dfs(v, u, depth + 1)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]: out.append([u, v])
            elif v != parent: low[u] = min(low[u], disc[v])
    dfs(0, -1, 0)
    return out

Cost

O(V + E) time and space for the one search, against O(E × (V + E)) for removing each edge and re-checking.

Common mistakes

• Skipping the parent by node when edges repeat: two edges between u and v are never a bridge, so skip only the edge you arrived by, by its index.
• Swapping the two conditions: > for bridges, >= for articulation points.
• Applying low[v] >= disc[u] to the root, where it always holds; the root is an articulation point only with two or more children in the search tree.
• Recursing 10⁵ levels deep in Python; write the search with an explicit stack.

Start with

• Critical Connections in a Network: every bridge, from one search.
• Minimum Number of Days to Disconnect Island: a whole island needs at most 2 days, and an articulation point makes it 1.

All biconnected component problems

Hard (2)

• Minimum Number of Days to Disconnect Island Array, Matrix, Depth-First Search
• Critical Connections in a Network Graph, Depth-First Search

Companies that ask biconnected component problems

• Amazon 2 problems on biconnected component
• Google 2 problems on biconnected component
• Microsoft 2 problems on biconnected component

Other topics

• Arrays 667 problems
• Strings 282 problems
• Math 213 problems
• Hash Table 202 problems
• Dynamic Programming 195 problems
• Greedy 163 problems
• Sorting 156 problems
• Two Pointers 113 problems
• Matrix 107 problems
• Binary Search 95 problems
• Simulation 88 problems
• Bit Manipulation 83 problems