Introduction

Weighted quick-union with path compression is the practical version of the union-find data structure. It supports two core operations: determine whether two elements belong to the same connected component, and merge two components efficiently. The reason it matters is that a naive implementation can degrade badly, while weighting and path compression make the operations so cheap that they are effectively constant time for real workloads.

The Problem Union-Find Solves

Imagine you are processing a stream of connections such as "connect 3 and 8" or "are 1 and 9 already connected?" You could store an explicit graph and run a traversal for every query, but that is wasteful when the only question is component membership.

Union-find stores a forest of trees:

• each set is one tree
• each node points to a parent
• the root of a tree identifies the component

The two main methods are:

• 'find(x): return the root that represents the component containing x'
• 'union(a, b): merge the components containing a and b'

Why Plain Quick-Union Is Not Enough

Basic quick-union represents each component as a parent tree, but it does not control tree shape. If unions happen in an unlucky order, the tree can become a long chain.

For example, after repeatedly attaching one root under another, you might end up with:

0 -> 1 -> 2 -> 3 -> 4

Then find(0) must walk through every parent pointer. That turns a conceptually simple operation into a linear-time one.

Weighting Keeps Trees Shallow

Weighted quick-union fixes that by always attaching the smaller tree under the larger tree. To do this, we track either the size or rank of each root.

If one component has 100 nodes and another has 3, it is clearly better to attach the smaller one under the larger one than the other way around. Repeating that rule keeps the trees shallow enough that find stays fast.

Path Compression Flattens Trees Further

Path compression improves find. Whenever you walk up from a node to its root, you update the visited nodes to point directly to that root.

That means a tree not only stays reasonably balanced because of weighting, but also gets flatter every time you query it. Future operations become even cheaper.

A classic implementation does both optimizations together.

Python Implementation

Here is a complete runnable implementation using size-based weighting and iterative path compression:

1class UnionFind:
2    def __init__(self, n):
3        self.parent = list(range(n))
4        self.size = [1] * n
5
6    def find(self, x):
7        root = x
8        while root != self.parent[root]:
9            root = self.parent[root]
10
11        while x != root:
12            parent = self.parent[x]
13            self.parent[x] = root
14            x = parent
15
16        return root
17
18    def union(self, a, b):
19        root_a = self.find(a)
20        root_b = self.find(b)
21        if root_a == root_b:
22            return False
23
24        if self.size[root_a] < self.size[root_b]:
25            root_a, root_b = root_b, root_a
26
27        self.parent[root_b] = root_a
28        self.size[root_a] += self.size[root_b]
29        return True
30
31    def connected(self, a, b):
32        return self.find(a) == self.find(b)
33
34
35uf = UnionFind(10)
36uf.union(1, 2)
37uf.union(2, 3)
38uf.union(7, 8)
39print(uf.connected(1, 3))
40print(uf.connected(1, 8))
41uf.union(3, 8)
42print(uf.connected(1, 8))

This implementation uses two passes in find: one to reach the root, and one to compress the path.

Why the Complexity Is So Good

The theoretical running time is often written as amortized O(alpha(n)) per operation, where alpha is the inverse Ackermann function. That sounds intimidating, but the practical interpretation is simple: it grows so slowly that it is below 5 for every input size you will ever see in real software.

So while the textbook answer is not "constant time," the engineering answer is close enough to constant time for most purposes.

Typical Uses

Union-find is especially good when connections are added over time and you need connectivity queries between additions.

Common examples include:

• Kruskal's minimum spanning tree algorithm
• dynamic network connectivity
• grouping pixels into connected components
• merging equivalence classes in compilers or symbolic systems

It is not a general graph structure. It does not answer shortest-path questions or support edge deletion well. It is specifically a data structure for connectivity and merging.

Common Pitfalls

The most common mistake is forgetting to call find before union. If you attach a directly to b rather than attaching root to root, the data structure becomes incorrect.

Another mistake is applying path compression incorrectly and overwriting parent pointers before you still need them. The two-pass implementation above avoids that issue cleanly.

Developers also sometimes think weighting and path compression are optional micro-optimizations. They are not. Without them, union-find can become slow enough to matter on large inputs.

Finally, do not use union-find for problems that require removing edges or enumerating explicit paths. That is outside its design.

Summary

• Union-find maintains disjoint sets and answers connectivity queries efficiently.
• Weighted quick-union keeps trees shallow by attaching smaller trees under larger ones.
• Path compression flattens trees during find operations.
• Together, these optimizations make operations effectively constant time in practice.
• Use the structure for dynamic connectivity, not for general-purpose graph traversal.