Graph Connectivity Decompositions: SCCs, Articulation Points & Biconnected Components

Connectivity is not a single yes/no property. In a directed graph, reachability may work in one direction but not the other. In an undirected graph, all vertices may currently be connected while one vertex or one edge is a hidden single point of failure. Connectivity decompositions turn those questions into explicit components and a smaller structural graph.

The two main settings use depth-first search (DFS), but their low-link values mean different things:

• directed: strongly connected components (SCCs) group vertices that can reach one another;
• undirected: bridges, articulation points, and biconnected blocks show where deleting one edge or vertex breaks connectivity.

Do not copy a recurrence from one setting into the other. The stack membership test in Tarjan’s SCC algorithm and the parent-edge rule in undirected DFS are different invariants.

Connectivity questions and their outputs #

All of these decompositions are for a static snapshot. Maintaining them under arbitrary insertions and deletions is a dynamic graph problem with a different cost model.

Strongly connected components #

In a directed graph $G=(V,E)$, vertices $u$ and $v$ are strongly connected when each is reachable from the other. This relation is:

• reflexive: every vertex reaches itself by a zero-edge path;
• symmetric by definition;
• transitive: paths $u\leadsto v\leadsto w$ and $w\leadsto v\leadsto u$ compose.

It is therefore an equivalence relation, and its equivalence classes partition $V$. An SCC is a maximal such class. “Maximal” matters: two overlapping mutually reachable sets belong to one larger SCC, not two components.

A singleton vertex is always an SCC. It contains a directed cycle only if it has a self-loop; membership in an SCC does not itself imply a nonempty cycle.

The condensation graph is a DAG #

Contract every SCC to one component vertex. For each original edge $u\to v$ whose endpoints have different component IDs, add

$$C(u)\to C(v).$$

Deduplicating parallel component edges gives the condensation graph. It must be acyclic. If distinct components lay on a directed component cycle, every vertex in each component could follow the cycle to every other component and return. Their union would be mutually reachable, contradicting SCC maximality.

This contraction separates cyclic internal behavior from acyclic global flow. Topological reasoning becomes valid on the condensation even when it is invalid on the original graph.

When building the condensation, component labels are arbitrary identifiers. Some SCC implementations happen to emit sink components first, but downstream code should topologically sort the constructed DAG unless the API explicitly promises an order.

Tarjan’s one-pass SCC algorithm #

Tarjan’s algorithm assigns each vertex a discovery index index[u], maintains low[u], and keeps active vertices on a stack. on_stack[u] means that $u$ has been discovered but not yet assigned to a completed SCC.

time = 0
stack = empty

strong_connect(u):
    index[u] = low[u] = time
    time += 1
    push u
    on_stack[u] = true

    for each directed edge u -> v:
        if index[v] is undefined:
            strong_connect(v)
            low[u] = min(low[u], low[v])
        else if on_stack[v]:
            low[u] = min(low[u], index[v])
        else:
            ignore the edge for low-link purposes

    if low[u] == index[u]:
        start a new component
        repeat:
            v = pop stack
            on_stack[v] = false
            assign v to this component
        until v == u

for every vertex u with undefined index:
    strong_connect(u)

For an active vertex $u$, low[u] summarizes the smallest discovery index that $u$’s still-active DFS region can reach without leaving the unresolved stack structure. The two update cases carry different evidence:

1. after recursively visiting a tree child $v$, the child’s entire unresolved region is known, so propagate low[v];
2. for an edge to an already discovered vertex $v$ that is still on the stack, the edge directly reaches index[v].

An edge to a completed SCC is ignored. That component has already been sealed; letting its old low value flow backward could incorrectly merge components that have only one-way reachability.

Why low[u] == index[u] closes one SCC #

If equality holds after all outgoing edges are processed, no active descendant in $u$’s DFS region can reach an active vertex discovered before $u$. Vertex $u$ is the earliest active vertex reachable from that region. The consecutive stack suffix from the top through $u$ is mutually reachable through DFS-tree paths downward and recorded return paths within the active region, so it forms one SCC. Popping the entire suffix makes the maximal component permanent.

Each vertex is pushed and popped once and each edge is examined once. With adjacency lists, time is $O(|V|+|E|)$ and auxiliary space is $O(|V|)$, in addition to the graph. An adjacency matrix still costs $\Theta(|V|^2)$ to scan because finding outgoing edges is no longer proportional to their count.

A complete SCC trace #

Use these directed edges, scanning them in the order shown:

A -> B
B -> C, D
C -> A
D -> E
E -> D, F
F -> (none)

DFS discovers A,B,C,D,E,F with indices 0 through 5.

The SCCs are {A,B,C}, {D,E}, and {F}. The condensation is the chain

$$\{A,B,C\}\longrightarrow\{D,E\}\longrightarrow\{F\}.$$

The edge B→D does not merge the first two SCCs because no path returns from {D,E} to {A,B,C}.

A two-pass alternative #

Kosaraju’s algorithm runs DFS once to compute decreasing finish order, then runs DFS in that order on the transposed graph. Each second-pass tree is one SCC. It has the same $O(V+E)$ asymptotic time and is often easier to derive from existing traversal primitives, but it needs reverse adjacency or an explicit transpose and two graph passes. Tarjan avoids the transpose at the cost of a more delicate active-stack invariant.

Undirected low-link values #

Now let $G$ be undirected. Give every undirected edge a unique ID and store two adjacency entries with that same ID. DFS records discovery time tin[u]. For a DFS-tree vertex $u$, define low[u] as the smallest discovery time reachable by:

1. descending zero or more DFS-tree edges within $u$’s subtree; then
2. using at most one non-tree edge to an ancestor.

Initialize low[u]=tin[u]. For a tree edge from $u$ to an undiscovered child $v$, recurse and then use

$$low[u]\gets\min(low[u],low[v]).$$

For a non-tree edge from $u$ to an already discovered ancestor $v$, use

$$low[u]\gets\min(low[u],tin[v]).$$

In an undirected DFS, every non-tree edge connects an ancestor and a descendant. Process it from the descendant endpoint, where tin[v] < tin[u]; this orientation also lets an edge stack store it exactly once.

The parent exception is an edge, not a vertex #

The tree edge by which DFS entered $u$ appears again in $u$’s undirected adjacency list. Skip that exact parent_edge_id. Do not skip every neighbor equal to parent[u].

If two parallel edges connect parent $p$ and child $u$, one may be the tree edge while the other is a legitimate non-tree edge back to $p$. The second edge lowers low[u] to tin[p], proving that neither parallel edge is a bridge. A parent-vertex check loses that evidence and produces a false bridge.

Self-loops never connect two previously separated vertex regions, so they cannot be bridges and cannot make a vertex an articulation point. Report them separately from connectivity blocks; otherwise a loop-only “block” can make the usual block-cut forest incidence convention ambiguous.

Bridges: the strict low-link boundary #

An undirected edge is a bridge if deleting it increases the number of connected components. A DFS-tree edge $(u,v)$, where $u$ is the parent, is a bridge exactly when

$$low[v] > tin[u].$$

If the inequality is strict, no vertex in $v$’s subtree has a non-tree edge to $u$ or any ancestor of $u$. The tree edge is therefore the subtree’s only connection to the earlier graph. Conversely, if low[v] <= tin[u], the subtree has a return edge reaching $u$ or above, and tree paths plus that edge form a route around $(u,v)$.

Every bridge belongs to the DFS tree; a non-tree edge already closes a cycle and therefore has an alternate path between its endpoints.

Removing every bridge leaves the 2-edge-connected components (also called bridge-connected components): maximal vertex sets in which every pair has two edge-disjoint connecting paths. These components form a vertex partition. Contracting them and retaining the bridges produces a forest.

Articulation points: root and non-root rules differ #

An articulation point or cut vertex is a vertex whose deletion, together with its incident edges, increases the number of connected components.

For a non-root DFS vertex $u$, the condition is

$$\exists\text{ tree child }v:\quad low[v]\ge tin[u].$$

The non-strict inequality is intentional. If the best return from $v$’s subtree reaches $u$ itself but no proper ancestor, deleting $u$ still separates that subtree from the earlier graph.

For a DFS root $r$, the correct condition is different:

$$r\text{ is an articulation point}\iff r\text{ has at least two DFS-tree children.}$$

Different root children cannot have an undirected edge between their subtrees; if such an edge existed, DFS would have reached the later child through the first subtree. Deleting the root therefore separates those child subtrees. With zero or one child, removing the root cannot split its DFS tree into multiple remaining regions.

The difference between bridge > and articulation >= captures two failure models. A return edge from a child subtree to $u$ itself gives an alternate route around the tree edge, so that edge is not a bridge. But every such route still passes through vertex $u$, so deleting the vertex disconnects the subtree.

Worked undirected decomposition #

Consider:

• triangle A-B-C-A;
• edge B-D;
• triangle D-E-F-D;
• leaf edge D-G.

With DFS tree edges A-B, B-C, B-D, D-E, E-F, D-G, discovery and low values are:

Consequences:

• B-D is a bridge because $low[D]=3>tin[B]=1$;
• D-G is a bridge because $low[G]=6>tin[D]=3$;
• B is an articulation point because child D has $low[D]\ge tin[B]$;
• D is an articulation point because children E and G cannot reach above D;
• root A has one DFS child, so it is not an articulation point.

Under the block convention used below, the vertex-biconnected blocks are the two triangles {A,B,C} and {D,E,F}, plus bridge blocks {B,D} and {D,G}.

Now add a second parallel edge between D and G. One D-G edge becomes the tree edge and the other becomes a return edge, so low[G]=tin[D]=3. Neither parallel edge is a bridge because the bridge test is strict. Vertex D remains an articulation point because $low[G]\ge tin[D]$: deleting D still isolates G from the rest.

Vertex-biconnected blocks #

A connected undirected graph is vertex-biconnected when it has no articulation point under the chosen small-graph convention. A block decomposition represents maximal regions that cannot be split by deleting an internal vertex.

Terminology for graphs with fewer than three vertices varies. This chapter uses the common edge-block convention useful in implementations:

• every non-loop edge belongs to exactly one block;
• a bridge forms a two-vertex, one-edge block;
• articulation vertices may occur in several blocks;
• isolated vertices are reported separately as singleton components;
• self-loops, if supported, are reported separately and do not affect low-link tests.

This convention distinguishes vertex blocks from 2-edge-connected components. Removing bridges produces a vertex partition. Vertex-biconnected blocks instead partition the non-loop edges, while articulation vertices are shared between blocks.

Extracting blocks with an edge stack #

Push every DFS-tree edge when traversed. Push a non-tree edge only from its descendant endpoint to its ancestor, so each undirected edge enters the stack once. After returning from child $v$ of $u$, whenever

$$low[v]\ge tin[u],$$

pop through the tree edge $(u,v)$. Those popped edges form one block. They cannot connect above $u$ without passing through $u$, and delaying the pop would incorrectly merge across an articulation boundary.

The following implementation simultaneously finds bridges, articulation points, and edge blocks. edges[eid] stores the endpoints; each non-loop adjacency entry carries the same stable eid at both endpoints.

def decompose_undirected(vertex_count, edges):
    adjacency = [[] for _ in range(vertex_count)]
    blocks = []
    loop_edges = []

    for edge_id, (a, b) in enumerate(edges):
        if a == b:
            loop_edges.append(edge_id)
        else:
            adjacency[a].append((b, edge_id))
            adjacency[b].append((a, edge_id))

    tin = [-1] * vertex_count
    low = [-1] * vertex_count
    edge_stack = []
    bridges = set()
    articulations = set()
    time = 0

    def dfs(u, parent_edge=-1):
        nonlocal time
        tin[u] = low[u] = time
        time += 1
        tree_children = 0

        for v, edge_id in adjacency[u]:
            if edge_id == parent_edge:
                continue

            if tin[v] == -1:
                tree_children += 1
                edge_stack.append(edge_id)
                dfs(v, edge_id)
                low[u] = min(low[u], low[v])

                if low[v] > tin[u]:
                    bridges.add(edge_id)

                if low[v] >= tin[u]:
                    if parent_edge != -1:
                        articulations.add(u)

                    block = []
                    while True:
                        popped = edge_stack.pop()
                        block.append(popped)
                        if popped == edge_id:
                            break
                    blocks.append(block)

            elif tin[v] < tin[u]:
                # Process each undirected non-tree edge only at its
                # descendant endpoint; parallel parent edges land here.
                edge_stack.append(edge_id)
                low[u] = min(low[u], tin[v])

        if parent_edge == -1 and tree_children >= 2:
            articulations.add(u)

    for root in range(vertex_count):
        if tin[root] == -1:
            dfs(root)
            assert not edge_stack

    nonloop_isolated = [u for u in range(vertex_count) if not adjacency[u]]
    return (bridges, articulations, blocks, nonloop_isolated,
            loop_edges, tin, low)

The comment records a correctness constraint rather than implementation history: changing the comparison to v != parent[u] breaks parallel-edge handling. The algorithm examines each adjacency entry a constant number of times, and every edge is pushed and popped at most once, so it runs in $O(V+E)$ time and uses $O(V+E)$ auxiliary/output storage.

The returned nonloop_isolated list includes a vertex carrying only self-loops because loops were intentionally excluded from connectivity adjacency. The separate loop_edges result preserves those edges without pretending that they affect connectivity. If an API defines loop-degree differently, expose separate “no non-loop incident edge” and “degree zero” predicates rather than silently changing the decomposition contract.

The block-cut forest #

Create one node for every vertex-biconnected block and one node for every articulation vertex. Connect articulation node $a$ to block node $B$ exactly when $a$ belongs to $B$.

For each original connected component containing an edge, this block-cut graph is a tree; across a disconnected graph it is a forest. It is connected because adjacent original blocks meet through their cut vertices. It cannot contain a cycle: a cycle would give two distinct block-level routes between shared cut vertices, contradicting the maximal separation of the blocks. An isolated original vertex can be added as a singleton block node when a uniform representation of every connected component is useful.

The block-cut forest answers structural queries cleanly:

• removing an articulation node separates the incident block branches;
• the unique block-cut path shows which cut vertices mediate travel between two robust regions;
• dynamic programming can operate on the forest after complex cyclic interiors are contracted.

Do not confuse it with the bridge forest. The bridge forest contracts 2-edge-connected vertex components and keeps bridges as edges. The block-cut forest represents vertex blocks and cut vertices as two different node types.

Correctness checklist for low-link code #

The following properties should be test assertions, not informal expectations:

1. tin[u] is assigned once, and low[u] <= tin[u] after DFS finishes $u$.
2. The exact undirected parent edge ID is skipped once; a parallel parent edge is processed normally.
3. A tree edge $(u,v)$ is a bridge exactly when low[v] > tin[u].
4. A non-root $u$ is an articulation point exactly when some child has low[v] >= tin[u].
5. A DFS root is an articulation point exactly when it has at least two tree children.
6. Every non-loop edge appears in exactly one emitted vertex block under this chapter’s convention.
7. Contracted SCC edges never form a directed cycle.

Useful adversarial fixtures include an isolated vertex, one edge, a simple cycle, a path, two cycles sharing one vertex, parallel edges, a self-loop, and a disconnected union of all of them.

Boundaries and common mistakes #

Disjoint-Set Union is excellent for connectivity under edge insertions and for Kruskal-style processing, but it does not retain the DFS ancestry and return-edge evidence needed to identify cuts. Graph Traversals supplies the discovery/finish-state foundation, while Graph Representations explains why stable edge identity is part of a multigraph API rather than an optional optimization.

Recursion depth is another operational boundary. A path graph produces depth $V$. Languages with shallow call stacks need an explicit frame stack that stores the current vertex, parent edge ID, and next adjacency position. Merely pushing bare vertices changes the return-time at which low[child] becomes available and is not an equivalent translation.

Choosing the decomposition #

The asymptotic result assumes the graph snapshot and its adjacency lists fit the computational model. Extremely large graphs can make adjacency layout and I/O dominate even though the abstract algorithm is linear.

Exercises #

1. Prove directly that contracting SCCs cannot introduce a directed cycle between distinct components.
2. In a DFS tree, give an example where low[child] == tin[parent]. Explain why the tree edge is not a bridge but the parent can be an articulation point.
3. Run the undirected algorithm on two vertices joined by two parallel edges. Record the edge stack and every inequality.
4. Explain why an undirected DFS has no non-tree edge between two unrelated DFS subtrees.
5. Compare the partitions produced by deleting all bridges with the overlapping vertex sets of biconnected blocks on two triangles sharing one vertex.