Disjoint set union for connected components

A connected component is a maximal group of vertices in which every pair is joined by some path. Graphs can contain many such groups: households in a social network, patches in an image, or stations reachable through a rail network. The challenge is to discover these groups without repeatedly traversing every edge.

A disjoint set union, commonly called union-find, maintains a partition of vertices into non-overlapping sets. It is especially effective when edges arrive incrementally, because each new edge can trigger an amortised near-constant merge while expensive path searches are avoided. The result is an exact component structure with a very small memory footprint.

Approach	Best suited to	Cost for component questions	Memory	Main limitation
Disjoint set union	Incremental undirected connectivity	O(α(n)) amortised per operation	O(n)	Does not retain edge paths or support easy splitting
BFS or DFS	Repeated traversal of a fixed graph	O(V + E) per traversal	O(V + E)	Must revisit edges after changes
Adjacency matrix	Small, dense graphs	O(V²) for a traversal	O(V²)	Wastes memory for sparse graphs

The mental model

An undirected graph says that an edge between u and v works in both directions. If u belongs to component A and v belongs to component B, observing that edge proves A and B are really one component. DSU records that fact by making both vertices point toward the same representative, also called a root.

This resembles transport disruptions in Sydney and Melbourne. A cancelled train connection may split one passenger network into separate reachable groups, while a new interchange can join groups that previously had no path between them. DSU captures the connectivity consequence of each change, although it does not preserve the train routes themselves.

A DSU therefore stores equivalence classes rather than adjacency lists. Every vertex has one parent pointer; each root represents a complete component. The representative may change after a merge, but the identity of the component remains correct. That distinction lets the structure use little space and answer repeated connectivity questions efficiently.

Core operations and invariants

A useful DSU exposes three operations. make_set(x) creates a singleton component, find(x) returns the representative containing x, and union(a, b) merges the components containing a and b. Most implementations create every singleton during initialisation, so application code only needs find and union while processing data.

find follows parent pointers until it reaches a root. union first finds both roots; if they match, nothing changes. Otherwise, it attaches one root beneath the other. Attaching the smaller tree beneath the larger one is called union by size, while attaching the lower-ranked tree beneath the higher-ranked one is union by rank. Both techniques limit tree height.

The central invariant is simple: two vertices have the same root exactly when they are connected in the graph processed so far. An isolated vertex remains its own root. A successful union reduces the component count by one, whereas an edge within an existing component leaves the count unchanged. Keeping this invariant explicit makes implementation and testing much easier.

Finding, merging, and compressing paths

Without an optimisation, repeated parent traversals could make queries slow. Path compression solves this by redirecting visited vertices toward their root. The following Python class uses path halving, a compact form of compression: each visited node is linked to its grandparent, and traversal continues from there.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.component_count = n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)

        if root_a == root_b:
            return False

        if self.size[root_a] < self.size[root_b]:
            root_a, root_b = root_b, root_a

        self.parent[root_b] = root_a
        self.size[root_a] += self.size[root_b]
        self.component_count -= 1
        return True

    def groups(self):
        buckets = {}
        for vertex in range(len(self.parent)):
            root = self.find(vertex)
            buckets.setdefault(root, []).append(vertex)
        return list(buckets.values())

The iterative find avoids recursion-depth problems, and groups performs one final pass to collect vertices under their roots. A union that returns False means the edge closes a cycle because its endpoints were already connected. This signal is useful in minimum spanning tree algorithms, although it is not needed merely to label components.

Component labels deserve particular care. The root integer is an implementation detail, not a permanent component name. Applications needing names that remain stable across updates should maintain an explicit component identifier and merge its mapping during unions. Otherwise, a later union could silently change the label of an existing group.

Building components from graph data

For an edge list, the construction algorithm is short: create one DSU element per vertex, process every edge, and call union(u, v). The number of successful merges is the initial vertex count minus the final number of connected components. The order in which edges arrive does not affect the resulting partition.

create a singleton set for every vertex
for each undirected edge (u, v):
    union(u, v)
for each vertex:
    place the vertex in the group of find(vertex)

Real inputs often use strings, such as Australian suburb names or customer IDs, rather than integer indices. Convert each distinct label to a stable integer once, store that label-to-index mapping, and perform DSU operations on the indices. This avoids repeated dictionary lookups inside the hot loop and prevents different labels from being confused because they happen to share a value.

Repeated edges, self-loops, and isolated vertices need explicit handling. Repeated edges are harmless because a redundant union changes nothing; self-loops also leave a singleton or existing component intact. Isolated vertices must still be included during initialisation, or they will disappear from the final groups. Duplicate edges should not be counted as evidence of separate connections.

Complexity, scaling, and memory

With path compression and union by size or rank, each find and union takes amortised O(α(n)) time, where α is the inverse Ackermann function. For every practical input size, α(n) is so small that operations are usually treated as effectively constant time. Building components from n vertices and m edges therefore costs O(n + m α(n)), close to the O(n + m) work of a single graph traversal.

Memory usage is O(n) because the DSU keeps one parent value and usually one size or rank value per vertex. It does not retain the original edges, which makes it attractive when the edge stream is large but only final membership matters. The trade-off is that the structure cannot list the path between two vertices or explain why they are connected.

Large Australian datasets often span more than one city or region. A service covering Sydney, Melbourne, Brisbane, and Perth may process partitioned graphs, then reconcile identifiers across partitions that later interact. Engineers in different Australian time zones also need reproducible batching rules, but a shared data definition matters more than the local clock: the same edge set must always produce the same partition.

Implementation patterns and language choices

DSU works well with contiguous integer indices and in-memory arrays. In Python, lists make the parent and size arrays straightforward. In C, the same design uses integer arrays rather than node objects; the site's C programming guide is useful for the array, pointer, and allocation details needed in a portable implementation.

In many Australian software interviews, candidates are expected to explain assumptions, derive the complexity, and test edge cases before coding. A DSU solution is a good fit for that format: the API is small, the invariant is easy to state, and union-find performance gives a clear reason for the data structure. The same reasoning works well in community coding meetups in Melbourne and Brisbane.

A reliable implementation checklist

• Map external labels to stable integer indices before processing edges.
• Initialise every vertex, including isolated and future vertices.
• Apply union by size or rank whenever two roots differ.
• Run a final grouping pass if actual component memberships are required.

Common failure modes to avoid

• Calling find only once per edge and assuming the other endpoint is already a root.
• Using a recursive find without checking that its recursion depth is bounded.
• Treating a redundant union as a successful merge in algorithms that detect cycles.
• Confusing a temporary root identifier with a permanent component label.

These safeguards keep the implementation readable while preserving the amortised bound. They also make test cases easier to construct: a single edge, a duplicate edge, an isolated vertex, and a long chain of merges exercise most of the important behaviour.

Where the technique fits in practice

DSU appears whenever connectivity is added but rarely removed. Typical uses include grouping social-network contacts, labelling connected regions in images, tracking service outages, and selecting edges for minimum spanning trees. In the Australian market, logistics platforms, property portals, and event-ticket services all encounter variants of these problems as locations, listings, or attendees gain relationships.

A very large ingestion pipeline can add a probabilistic filter before exact lookups. A space-efficient membership guide explains how a Bloom filter can reject most unknown identifiers with little memory. It complements DSU rather than replacing it: false positives are possible, while DSU provides exact connectivity once an identifier is known to exist.

Several boundaries are worth remembering. DSU handles undirected connectivity, not strongly connected components in a directed graph. It does not support splitting a component after edges are removed, because union-find has no efficient inverse operation. It also answers membership through find, but reconstructing every group requires an extra pass. Applications needing edge history, deletion, or directed reachability need a different model.

The enduring idea is to treat connectivity as a partition that can grow through merges. When that matches the problem, union by size and path compression deliver an elegant combination of exact answers, near-constant amortised time, and O(n) memory.