Biconnected Components

Biconnected Components is a classic graph problem that pushes the articulation-point DFS one step further. Instead of just naming the cut vertices, we partition the graph's edges into maximal chunks that have no internal articulation point. The trick is to carry an edge stack alongside the usual disc/low values.

The slow way first

You could test, for every edge, which other edges lie on a common simple cycle with it, then group them. Building those relationships pair by pair is painfully slow — roughly O(E²) or worse, and the cycle reasoning is fiddly to get right.

The question to ask: as DFS walks the graph, can I recognize the boundary of one component the instant I cross it? The boundary is exactly an articulation point, and DFS already detects those with disc/low.

The idea: one DFS with an edge stack

Run a single DFS. Give every vertex a discovery time disc[u] and a low[u] — the earliest discovery time reachable from u's subtree using one back edge. Push every edge onto a stack the first time you traverse it. When you return from a child v and find low[v] >= disc[u], vertex u is an articulation point: pop edges off the stack down to and including (u, v) — those popped edges are exactly one biconnected component.

The key insight: the stack holds edges in the order we discovered them, so the edges of one component are always a contiguous block on top of the stack by the time we close it.

Walk through it

Step through the animation. DFS dives 0 → 1 → 2, pushing each tree edge. The back edge 2 → 0 pulls low[2] down to 0, fusing the first triangle. DFS then explores 2 → 3 → 4, and the back edge 4 → 2 fuses the second triangle. Returning to 2, the child 3 satisfies low[3] >= disc[2], so we pop the second component. Finally the root 0 closes the first component.

Pseudocode

dfs(u, parent):
    disc[u] = low[u] = timer++          # discovery time
    for each neighbor v of u:
        if v is unvisited:
            push edge (u, v) on the stack
            dfs(v, u)
            low[u] = min(low[u], low[v])
            if low[v] >= disc[u]:        # u is an articulation point
                pop edges down to (u, v) into one component
        else if v != parent and disc[v] < disc[u]:
            push back edge (u, v); low[u] = min(low[u], disc[v])

The Python solution

def bcc(u, parent):
    nonlocal timer
    disc[u] = low[u] = timer; timer += 1
    for v in graph[u]:
        if v not in disc:
            stack.append((u, v))
            bcc(v, u)
            low[u] = min(low[u], low[v])
            if low[v] >= disc[u]:
                comp = []
                while stack[-1] != (u, v):
                    comp.append(stack.pop())
                comp.append(stack.pop())
                components.append(comp)
        elif v != parent and disc[v] < disc[u]:
            stack.append((u, v))
            low[u] = min(low[u], disc[v])

• disc[u] = low[u] = timer stamps the discovery order; low[u] will shrink as back edges are found.
• For an unvisited neighbor v we push the tree edge, recurse, then pull low[u] down by low[v].
• Line 9 is the heart: low[v] >= disc[u] means nothing in v's subtree reaches above u, so u is an articulation point and a component ends here.
• The while loop pops edges down to and including (u, v) — that contiguous block is one biconnected component.
• The elif handles a back edge to an already-visited ancestor (not the parent): push it and lower low[u] using the ancestor's disc.

Complexity

The single DFS touches every vertex and every edge a constant number of times, and the stack holds at most every edge once — so both time and space are linear in the size of the graph.

When this pattern shows up

Practice