Bridges, Articulation Points and Biconnected Components

This is an extension topic beyond most interviews; it pays off for "critical connections" and "single point of failure" questions, which show up in hard rounds and network-reliability OAs.

Intuition

In a connected undirected graph:

• a bridge is an edge whose removal disconnects the graph;
• an articulation point (cut vertex) is a vertex whose removal disconnects it.

Trying every removal costs O(m (n + m)). One DFS does it in linear time thanks to a special property of undirected DFS trees: every non-tree edge joins a vertex to one of its ancestors (there are no cross edges). So the only way for a subtree to "escape" upward is through a back edge.

Give every vertex its discovery time dfn[v], and define low[v] as the smallest discovery time reachable from v's subtree using tree edges downward plus one back edge, without reusing the edge to the parent. Then, for a tree edge u -> v (u is the parent):

• low[v] > dfn[u]: nothing in v's subtree reaches u or above, so the edge u-v is a bridge;
• low[v] >= dfn[u]: nothing reaches strictly above u, so removing u cuts v's subtree off. u is an articulation point, except the DFS root, which is one exactly when it has two or more DFS children.

Removing all bridges splits the graph into 2-edge-connected components: inside each, every pair of vertices has two edge-disjoint paths. The vertex version (biconnected components, or blocks) groups edges instead of vertices, and two blocks can share an articulation point; it is built by pushing edges on a stack and popping a block whenever low[v] >= dfn[u], which is rarely needed in interviews.

When to use it in interviews / OAs

• "Critical connections in a network": list all bridges.
• "Which servers or routers are single points of failure": articulation points.
• "Minimum number of cells to remove to disconnect an island": the answer is 0, 1 or 2, and it is 1 exactly when the land has an articulation point (or is a single cell).
• "Group nodes that stay connected after any single link fails": 2-edge-connected components, then reason about the tree of components ("bridge tree").

Template

One DFS for bridges and articulation points

Edge ids (instead of parent vertices) make parallel edges work: two edges between the same pair are never bridges.

def bridges_and_cut_vertices(n: int, edges: list[tuple[int, int]]) -> tuple[list[int], list[int]]:
    # returns (ids of bridge edges, articulation points); iterative DFS
    adj: list[list[tuple[int, int]]] = [[] for _ in range(n)]
    for i, (u, v) in enumerate(edges):
        adj[u].append((v, i))
        adj[v].append((u, i))
    dfn = [-1] * n
    low = [0] * n
    timer = 0
    bridges, is_cut = [], [False] * n
    for root in range(n):
        if dfn[root] != -1:
            continue
        dfn[root] = low[root] = timer
        timer += 1
        root_children = 0
        work = [(root, -1, iter(adj[root]))]  # (vertex, id of its tree edge, edge iterator)
        while work:
            u, pe, it = work[-1]
            for v, eid in it:
                if eid == pe:
                    continue  # never climb back over our own tree edge
                if dfn[v] == -1:
                    dfn[v] = low[v] = timer
                    timer += 1
                    work.append((v, eid, iter(adj[v])))
                    break
                low[u] = min(low[u], dfn[v])  # back edge to an ancestor
            else:  # u finished: report to its parent p
                work.pop()
                if work:
                    p = work[-1][0]
                    low[p] = min(low[p], low[u])
                    if low[u] > dfn[p]:
                        bridges.append(pe)
                    if p == root:
                        root_children += 1
                    elif low[u] >= dfn[p]:
                        is_cut[p] = True
        if root_children >= 2:
            is_cut[root] = True
    return bridges, [v for v in range(n) if is_cut[v]]

2-edge-connected components

def two_edge_components(n: int, edges: list[tuple[int, int]]) -> list[int]:
    bridge_ids = set(bridges_and_cut_vertices(n, edges)[0])
    adj: list[list[int]] = [[] for _ in range(n)]
    for i, (u, v) in enumerate(edges):
        if i not in bridge_ids:  # drop bridges, keep everything else
            adj[u].append(v)
            adj[v].append(u)
    comp, c = [-1] * n, 0
    for s in range(n):
        if comp[s] != -1:
            continue
        comp[s] = c
        stack = [s]
        while stack:
            u = stack.pop()
            for v in adj[u]:
                if comp[v] == -1:
                    comp[v] = c
                    stack.append(v)
        c += 1
    return comp

Application: minimum days to disconnect an island

def min_days_to_disconnect(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    cells = [(r, c) for r in range(rows) for c in range(cols) if grid[r][c] == 1]
    idx = {cell: i for i, cell in enumerate(cells)}
    edges = [(idx[(r, c)], idx[(r + dr, c + dc)]) for r, c in cells
             for dr, dc in ((1, 0), (0, 1)) if (r + dr, c + dc) in idx]
    n = len(cells)
    if n == 0 or len(set(_component_ids(n, edges))) != 1:
        return 0  # already disconnected (or no land)
    if n == 1 or bridges_and_cut_vertices(n, edges)[1]:
        return 1  # one removal splits it
    return 2  # any cell can be isolated by removing at most two neighbours


def _component_ids(n: int, edges: list[tuple[int, int]]) -> list[int]:
    parent = list(range(n))

    def find(x: int) -> int:
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for u, v in edges:
        parent[find(u)] = find(v)
    return [find(v) for v in range(n)]

Complexity

One DFS: O(n + m) time, O(n + m) memory for the adjacency lists. Components afterwards add O(n + m). The island application is linear in the grid size.

Common pitfalls

• Skipping the parent vertex instead of the parent edge. With parallel edges, the second copy is a legitimate back edge; skipping by vertex wrongly reports a bridge.
• Root rule. The root is an articulation point only with at least two DFS children; the low >= dfn test would flag it almost always.
• > vs >=. Bridges use low[v] > dfn[u]; articulation points use low[v] >= dfn[u]. Swapping them is the most common bug.
• low through tree edges vs. back edges. From a child, propagate low[child]; from a back edge, use dfn[ancestor].
• Disconnected input. Run from every unvisited vertex; bridges and cut vertices are defined per component.
• Recursion. A path of 10^5 vertices crashes a recursive Python DFS; keep the iterative form.

Interview variations

• Critical connections. Return [edges[i] for i in bridges].
• Minimum days to disconnect an island. 0, 1 or 2 as above; the brute-force alternative (try removing each cell and recount islands) is O((R C)^2), often still accepted for small grids.
• Bridge tree. Contract 2-edge-connected components; the bridges form a tree. Making the graph bridgeless needs ceil(leaves / 2) extra edges.
• Is the graph 2-edge-connected / biconnected? No bridges / no articulation points (and connected).
• Edges that lie on every path between s and t. They are exactly the bridges on the s-t path of the bridge tree.