Labelling Connected Components Once Versus Maintaining Them Under Insertions

Given an undirected graph, the connected components are the equivalence classes of the reachability relation. Computing them for a static graph is one of the cheapest things a traversal can do: a single pass over the vertices, launching a search wherever an unlabelled vertex appears, writes an identifier into every vertex and touches every edge once. The same question asked about a graph that changes between queries is a different problem with a different cost profile, and the boundary between the two is where most of the engineering interest lies.

One pass, one identifier per class

The labelling algorithm is breadth-first or depth-first search with a counter:

def components(adj):
    n = len(adj)
    comp = [-1] * n
    count = 0
    for s in range(n):
        if comp[s] != -1:
            continue
        comp[s] = count
        stack = [s]
        while stack:
            u = stack.pop()
            for v in adj[u]:
                if comp[v] == -1:
                    comp[v] = count
                    stack.append(v)
        count += 1
    return comp, count

The sentinel in the label array serves as the visited set, so the traversal needs no separate structure. Each vertex is labelled exactly once, and each edge is examined twice — once from each endpoint — because the adjacency lists store both directions. Total work is Θ(n + m) on a list representation. The number of components is the final value of the counter, which is also the number of times the outer loop found an unlabelled vertex.

Two properties of the result are worth stating precisely because later algorithms depend on them. First, the labels are arbitrary: any bijection of 0..c-1 onto the components yields an equally valid labelling, and comparing labels between two runs of the algorithm is meaningless unless the runs used the same vertex order. Second, the labelling is a partition, not a path: knowing that two vertices share a label says they are connected, not how. Recovering a path requires the parent pointers that the traversal could have recorded and this version discards.

For an undirected graph with no self-loops the counts satisfy n − m = c − r, where r is the cycle rank — the size of a cycle basis. Knowing r therefore gives c, but r is itself defined in terms of c, so the identity is a consistency check rather than a way to avoid the traversal.

Directed graphs need a different decomposition

Reachability in a directed graph is not symmetric, so “connected component” splits into two notions. Weak components ignore edge direction and are computed by the same traversal on the symmetrized graph — the adjacency lists plus the reverse lists merged. Strong components require that each pair of vertices reach each other; they are found either by a single depth-first pass that carries a lowlink value or by two passes over the graph and its transpose, using the lowlink values or the two-pass ordering that depth-first search makes available.

The distinction matters for cost. Weak components are Θ(n + m) and need the reverse adjacency only to build the symmetric list. Strong components are also Θ(n + m) but need a depth-first search that records discovery and finish order, which means the traversal must be able to produce that order, which in turn constrains the implementation choice discussed in the iterative DFS article. Algorithms that conflate the two produce a component count that is too small on any graph with a one-way edge between groups.

The online version of the same question

Suppose edges arrive one at a time and each arrival must be followed by a query: are u and v connected now? The static pass cannot be repeated per query — that is Θ(n + m) per edge, quadratic overall. Two structures handle the incremental case, and they sit at opposite ends of a trade.

A union-find structure maintains the partition directly. Each new edge merges two classes if their representatives differ, in time that is inverse-Ackermann per operation with union by rank and path compression; the classic bound is O(α(n)) amortized, where α grows so slowly that α(n) ≤ 4 for any n representable in practice. It answers connectivity queries but cannot answer “which vertices are in this component” without walking every vertex, and it cannot support deletions at all. The merge-only structure is the right tool exactly when the update stream is insertion-only.

A dynamic connectivity structure that supports deletions as well must do substantially more work. The standard approach is a spanning-forest maintained under updates, with a level structure that assigns each edge a level and searches for replacement edges when a tree edge is deleted. The best-known bounds for fully dynamic connectivity are polylogarithmic per operation in the number of vertices, but with constants and implementation complexity that make the static pass look trivial. For the common case of insertions plus occasional global recomputation, the practical answer is union-find plus a periodic relabelling pass, accepting stale labels between passes.

A third option exists for offline workloads: if all edges and all queries are known in advance, the queries can be answered by a divide-and-conquer over time using a rollback-capable union-find. That is the same trick used for offline dynamic connectivity in competitive settings, and it converts a hard online problem into a manageable offline one at the cost of storing the entire input.

Component labels as an index

Once computed, labels serve as a fast path in later queries. A connectivity test between two vertices becomes one array comparison instead of a search, and any algorithm that would otherwise run a traversal per query can instead group by label. This is the mechanism behind reachability caches in query planners, connected-component filters in image processing, and the island detection in flood-fill raster operations, where the grid is the graph and 4- or 8-neighbour adjacency defines the edges.

The index has a maintenance cost that is easy to underestimate. Every inserted edge either joins two components, in which case one entire label class must be rewritten, or stays inside one, in which case nothing changes. Rewriting a class costs the size of the smaller class if the implementation always relabels the smaller side, which gives an O(n log n) total bound over a sequence of merges — the same argument as union by size, applied to labels rather than to tree roots. Without that rule, a sequence of merges that always relabels the larger class costs Θ(n²).

Deletions invalidate the whole premise. Removing a bridge splits a component, and detecting whether a removed edge was a bridge requires knowing the component’s structure, not just its labels. An implementation that decrements a counter on deletion without checking will report a single component where two exist.

Where the linear pass is not the bottleneck

On graphs that fit in memory the traversal is fast enough that the surrounding I/O dominates. Reading an edge list in text form costs more than the labelling; parsing integers from lines is the expensive part, and the Θ(n + m) pass disappears into it. The same is true when the graph is materialized from a database or a serialized columnar format: the scan that builds the adjacency lists is the cost, and the traversal that follows is nearly free by comparison.

For graphs that do not fit, the pass becomes the problem. A component labelling over an external-memory graph must either hold the label array in memory — which is feasible when the vertex count is much smaller than the edge count, since the labels are 4 or 8 bytes per vertex — or spill it. The latter is why large-scale component labelling implementations keep the label array resident and stream the edge list, performing repeated passes until no label changes, an approach that converges in a number of passes proportional to the component diameter rather than to the graph size.

The final edge case is isolated vertices. A vertex with no edges is its own component, and the outer loop must still visit it. Implementations that build adjacency lists only for vertices that appear in the edge list, then iterate over the edge-derived vertex set, silently drop those vertices and undercount. The count of components in a graph with n vertices and no edges is n, and any labelling that returns 0 has failed on the simplest possible input.