Union-Find and Disjoint Sets

Connections arrive one at a time and you need to know what has become joined to what. Two ticker symbols on different venues turn out to be the same instrument. Two account IDs turn out to belong to the same client. Two assets cross a correlation threshold and belong in the same risk cluster. After every new link the questions are the same: are these two in the same group now, and how many groups are left?

You could rerun a graph traversal after each new edge, but that is $O(V+E)$ every time and you are doing it thousands of times. Union-find — also called a disjoint-set union, or DSU — answers both questions in effectively constant time.

The idea: every group has one representative

Picture each group as a club where everyone can point to their leader, possibly through a chain of people. The structure stores exactly one thing per element: a parent pointer. Follow parents upward until you reach someone who points at themselves — that person is the group's root, the representative.

Two operations do everything:

• find(x) — walk up from x to its root. Two elements are in the same group precisely when find returns the same root for both.
• union(a, b) — find both roots; if they differ, make one root point at the other. Two clubs become one, in a single pointer write.

Written naively this is $O(n)$ per operation, because the chains can grow long. Two small fixes change everything.

Union by size (or rank): when merging, always hang the smaller tree under the larger root. An element's depth only increases when its tree gets absorbed by a bigger one, which at most doubles the size, so depth stays $O(\log n)$.

Path compression: after find(x) locates the root, point every node you walked past directly at the root. The next query on any of them is one hop.

With both, the amortised cost of an operation is

$$O(\alpha(n))$$

where $\alpha$ is the inverse Ackermann function — a quantity that grows so absurdly slowly it is below 5 for any $n$ that fits in the universe. Treat it as constant, note in an interview that it is not literally constant, and move on.

Worked example: six items, four merges

Start with {0} {1} {2} {3} {4} {5} — six groups, everyone their own root.

• union(0,1): roots 0 and 1 differ, hang 1 under 0. Groups: 5.
• union(2,3): hang 3 under 2. Groups: 4.
• union(1,3): find(1) returns 0, find(3) returns 2. Both trees have size 2, so hang 2 under 0. Now {0,1,2,3}. Groups: 3.
• union(0,2): both find calls return 0. Same root already — do nothing. Groups stay at 3.

That last step is the one that matters. Detecting "already connected" is how union-find spots a cycle: if an edge joins two vertices that already share a root, adding it would close a loop.

class DSU:                              # ~O(1) amortised per operation
    def __init__(self, n):
        self.p = list(range(n))
        self.size = [1] * n
        self.count = n                  # number of groups

    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]   # path halving: compress as you climb
            x = self.p[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                # already together, no merge
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra             # smaller tree hangs under larger
        self.p[rb] = ra
        self.size[ra] += self.size[rb]
        self.count -= 1
        return True

Worked example: cycle detection inside Kruskal

Kruskal's algorithm for a Minimum Spanning Trees sorts edges by weight and adds them cheapest-first, skipping any edge that would create a cycle. Union-find is the cycle test. Given edges A–B (1), C–D (2), B–C (3), A–D (4) on four nodes: add A–B (union succeeds), add C–D (succeeds), add B–C (succeeds, everything is now one group of four), then try A–D — find(A) and find(D) return the same root, so union returns False and the edge is skipped. Three edges for four nodes, which is exactly what a spanning tree needs.

Where it shows up

In interviews: number of islands, accounts merge, redundant connection, friend circles, Kruskal's MST, and "is this graph a valid tree?". Recognising that a problem is really about incremental connectivity is most of the battle, and interviewers do ask you to state the amortised complexity and name the two optimisations.

In quant work, union-find groups assets into clusters once a correlation or cointegration test links them pairwise — a cheap first pass before Correlation Clustering or Hierarchical Risk Parity (López de Prado). Reference-data pipelines use it to fold many venue-specific symbols, ISINs and internal IDs into one canonical instrument as identity matches trickle in. Risk systems use it to find which positions are entangled through shared collateral or netting agreements, and post-trade systems use it to collapse fills that belong to the same parent order.