Introduction

Biconnected components describe the blocks of an undirected graph that do not fall apart when you remove one internal vertex. They are useful in network reliability, articulation-point analysis, and graph decomposition.

To output all of them, the standard tool is a depth-first search with discovery times, low-link values, and a stack of traversed edges. The stack is what lets you emit the actual component contents instead of only counting them.

Core Idea: DFS, disc, and low

During DFS, assign each vertex a discovery time disc[u]. Also compute low[u], the earliest discovery time reachable from u through tree edges and at most one back edge.

For an undirected edge from u to v:

• if v is unvisited, it becomes a DFS child
• if v is already visited and is not the parent, it is a back edge

The key condition is this:

• when low[v] >= disc[u], the edges on the stack from the most recent boundary up to (u, v) form one biconnected component

That happens because v and everything below it can no longer reach an ancestor of u without going through u.

Why an Edge Stack Is Needed

If you only compute articulation points, you can stop after maintaining disc and low. To output the components themselves, keep a stack of edges visited during DFS.

Whenever you traverse a tree edge or discover a back edge to an ancestor, push that edge. When low[v] >= disc[u], pop until (u, v) appears. Everything popped belongs to the same block.

This naturally handles cycles, shared articulation vertices, and bridge-like single-edge blocks.

Python Implementation

The following implementation outputs each component as a list of edges:

1from collections import defaultdict
2
3
4class BiconnectedComponents:
5    def __init__(self, n, edges):
6        self.n = n
7        self.graph = defaultdict(list)
8        for u, v in edges:
9            self.graph[u].append(v)
10            self.graph[v].append(u)
11
12        self.time = 0
13        self.disc = [-1] * n
14        self.low = [-1] * n
15        self.parent = [-1] * n
16        self.edge_stack = []
17        self.components = []
18
19    def run(self):
20        for u in range(self.n):
21            if self.disc[u] == -1:
22                self._dfs(u)
23                if self.edge_stack:
24                    self.components.append(self._pop_all())
25        return self.components
26
27    def _dfs(self, u):
28        self.disc[u] = self.low[u] = self.time
29        self.time += 1
30
31        for v in self.graph[u]:
32            if self.disc[v] == -1:
33                self.parent[v] = u
34                self.edge_stack.append((u, v))
35                self._dfs(v)
36                self.low[u] = min(self.low[u], self.low[v])
37
38                if self.low[v] >= self.disc[u]:
39                    component = []
40                    while self.edge_stack:
41                        e = self.edge_stack.pop()
42                        component.append(e)
43                        if e == (u, v) or e == (v, u):
44                            break
45                    self.components.append(component)
46
47            elif v != self.parent[u] and self.disc[v] < self.disc[u]:
48                self.low[u] = min(self.low[u], self.disc[v])
49                self.edge_stack.append((u, v))
50
51    def _pop_all(self):
52        component = self.edge_stack[:]
53        self.edge_stack.clear()
54        return component
55
56
57edges = [
58    (0, 1),
59    (1, 2),
60    (2, 0),
61    (1, 3),
62    (3, 4),
63    (4, 5),
64    (5, 3),
65]
66
67bcc = BiconnectedComponents(6, edges)
68for i, component in enumerate(bcc.run(), start=1):
69    print(f"component {i}: {component}")

For that graph, one component is the triangle among 0, 1, and 2, another is the cycle among 3, 4, and 5, and the edge from 1 to 3 forms its own block.

Converting Edge Blocks to Vertex Sets

Sometimes you want vertices rather than edges. That is easy once a component has been popped.

1def component_vertices(edge_component):
2    vertices = set()
3    for u, v in edge_component:
4        vertices.add(u)
5        vertices.add(v)
6    return sorted(vertices)

You can apply that helper to each emitted component:

for component in bcc.run():
    print(component_vertices(component))

Remember that articulation vertices can appear in more than one component. That is expected behavior, not a bug.

Complexity

The DFS visits each vertex once and examines each undirected edge a constant number of times. Time complexity is O(V + E), and the auxiliary memory is also O(V + E) because of the recursion state, arrays, and edge stack.

That is optimal for outputting all components, since reading the graph already costs O(V + E).

Common Pitfalls

The most common mistake is confusing bridges with biconnected components. A bridge edge can become a single-edge block in the decomposition, but the algorithm still uses the articulation condition low[v] >= disc[u] and a stack of edges.

Another bug is pushing too many back edges. In an undirected graph, only push a back edge when it goes to an ancestor. A simple check like disc[v] < disc[u] prevents duplicate handling.

Disconnected graphs are also easy to miss. You must start DFS from every unvisited vertex, not only vertex 0.

Finally, many implementations forget to flush the edge stack after finishing a connected component. If edges remain on the stack after one DFS root completes, they belong to one final block and should be emitted.

Summary

• Use DFS with discovery times and low-link values.
• Keep a stack of traversed edges so you can output actual components.
• Emit a component when low[v] >= disc[u].
• Articulation vertices may belong to multiple components.
• Handle disconnected graphs by starting DFS from every unvisited vertex.
• The full algorithm runs in O(V + E) time.