• V = number of elements, typically labelled 0 to V-1
• find(x) returns the representative of x's group; the specific value is arbitrary but consistent
• union(x, y) merges two groups; merging elements already grouped together is a no-op
• Connectivity is symmetric — the structure models undirected relationships only
• O(α(V)) amortised per operation with path compression and union by rank; O(V) space

Every graph technique so far answers connectivity by walking the graph. That works when the graph is fixed and you ask once. It fails badly under a different setting: connections arriving one at a time, with "are these two connected?" asked in between.

Suppose friendships are added to a social network one by one, and after each addition you must answer whether two given people are connected through any chain.

With a traversal, each query means a fresh search from one person to see whether the other is reachable — O(V + E) every time. With Q queries that is O(Q × (V + E)), and on a network of millions with constant updates it is hopeless.

The waste is structural rather than incidental. Each search rediscovers the entire shape of a group merely to answer a yes-or-no question about membership. The group has not changed since the last query, yet its structure is re-derived from scratch.

That suggests keeping the grouping as a maintained fact instead of a computed one.

Rather than storing which elements connect to which, store, for each element, a pointer toward a single distinguished member of its group — its representative, or root.

Now "are x and y connected?" becomes "do x and y have the same representative?" No searching, just two lookups and a comparison.

And merging two groups becomes cheap in a way that is genuinely surprising the first time. To merge, you do not touch the members at all. You take the representative of one group and point it at the representative of the other. Every element that followed the first representative now, by following one extra step, arrives at the second. One pointer write merges two groups of any size.

The structure formed is a forest: each group is a tree whose root points at itself, and find walks up from any element to its root.

parent = list(range(V))          # everyone starts as their own root

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

def union(x, y):
    rx, ry = find(x), find(y)
    if rx == ry:
        return False             # already together; nothing to do
    parent[rx] = ry              # one write merges two whole groups
    return True

The boolean returned by union is worth noting now, because several problems depend on it: it reports whether the merge actually did anything. A false return means the two were already connected — which, if you are adding a graph edge, means that edge closed a cycle.

The version above has a bad case. Merge 0 into 1, then 1 into 2, then 2 into 3, and so on. Each merge points the current root at the new element, producing a single chain of length V. Now find(0) walks V steps, and the structure is no better than the linear scan it replaced.

The problem is that the trees are allowed to grow tall. Two independent fixes keep them flat, and both are needed for the full guarantee.

Union by rank. When merging, attach the shorter tree under the taller one. Attaching a shorter tree under a taller root leaves the height unchanged, because the shorter tree's deepest element is still no deeper than the taller tree's. So height only increases when two trees of equal height merge — and then it grows by exactly one while the size at least doubles. Since size can double at most log₂V times before exceeding V, the height is capped at log₂V. Tracking approximate height rather than exact size is why the field is called rank.

Path compression. Whenever find walks from an element to the root, it has just learned the answer for every element along the way. So instead of discarding that, repoint each of them directly at the root on the way back. The next lookup for any of them takes one step. A tall chain gets flattened into a shallow star the first time it is traversed, so slow lookups pay for their own elimination.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n                        # number of groups, useful on its own

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])   # compress on the way back
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False                      # already connected
        if self.rank[rx] < self.rank[ry]:     # attach shorter under taller
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1                # heights were equal: the tree got taller
        self.count -= 1
        return True

With both optimisations, the amortised cost per operation is O(α(V)), where α is the inverse Ackermann function. The precise definition is not the point; the magnitude is. α grows so slowly that for any V that could be stored on any physical computer — beyond the number of atoms in the observable universe — α(V) is less than 5.

So each operation is constant time for every practical purpose, though not constant in the strict theoretical sense. Saying "effectively constant, formally inverse Ackermann" is exactly right in an interview.

Worth being precise about amortised: an individual find on a freshly built tall chain really can cost more than constant. But that call flattens the path it walked, so the cost cannot recur. Averaged over any sequence of operations, the per-operation cost is bounded by α.

Four elements, starting as {0}, {1}, {2}, {3}, with all ranks 0 and count 4.

That final false is the whole basis of cycle detection: an edge whose union is redundant is an edge that closes a loop.

Both approaches count components and detect cycles in undirected graphs, so the choice depends on the shape of the problem rather than the question.

Reach for Union-Find when the input is a list of edges rather than an adjacency structure; when edges arrive incrementally and connectivity must be queried between additions; when you need a running count of components; or when the question is specifically about whether adding an edge creates a cycle, which is a single find-comparison.

Reach for traversal when you need something about the structure rather than membership — the actual path between two nodes, distances, the vertices in each component, or anything at all about a directed graph.

Recognition signals: connected components, provinces, merging accounts, friend circles, detecting a redundant edge, building a minimum spanning tree. Kruskal's algorithm is Union-Find plus sorting the edges — you take each edge cheapest-first and keep it only if its union succeeds, which is exactly "keep it unless it closes a cycle".

Train the reflex: when connections accumulate over time and you keep being asked who is connected to whom, stop searching the graph. Give every group a name and merge names instead.