Real-World Use and Pitfalls

Union-find is not just an interview data structure. It lives inside graph libraries, image processing, compilers and data-cleaning pipelines. This chapter shows how real libraries expose it, lists common mistakes, and points to further reading.

Union-find in libraries

Before writing your own, check whether a library you already use provides one.

• SciPy: scipy.cluster.hierarchy.DisjointSet (since SciPy 1.6) accepts any hashable object as an element, not just integers.
• NetworkX: networkx.utils.UnionFind is used internally, for example by its Kruskal minimum spanning tree implementation.
• Boost: the C++ Boost Graph Library provides boost::disjoint_sets, used for incremental connected components.
• Image processing: connected-component labeling such as scikit-image's label or OpenCV's connectedComponents relies on the same idea to merge provisional labels in the classic two-pass algorithm.

from scipy.cluster.hierarchy import DisjointSet

ds = DisjointSet(["a", "b", "c", "d"])
ds.merge("a", "b")
ds.merge("c", "d")
print(ds.connected("a", "c"))   # False
ds.add("e")
ds.merge("b", "e")
print(sorted(map(sorted, ds.subsets())))  # [['a', 'b', 'e'], ['c', 'd']]

Where it shows up in real systems

• Networks and infrastructure: tracking which devices can reach each other as links are added.
• Data cleaning and entity resolution: grouping records that share a phone number, email or device ID into one customer.
• Compilers and type checkers: unification in type inference and Steensgaard-style points-to analysis merge things proven to be "the same" with union-find.
• Physics simulations: percolation experiments open random grid cells and check whether the top and bottom have become connected.
• Clustering: merging every pair of points closer than a threshold gives the same result as single-linkage clustering.

Handling string keys

Real data rarely comes with integer keys. Number each new key with a dictionary and the array-based DSU works unchanged.

class KeyedDSU:
    def __init__(self):
        self.index, self.parent, self.size = {}, [], []

    def _id(self, key):
        if key not in self.index:
            self.index[key] = len(self.parent)
            self.parent.append(len(self.parent))
            self.size.append(1)
        return self.index[key]

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

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True

d = KeyedDSU()
d.union("phone:555-0100", "mail:kim@x.io")
d.union("mail:kim@x.io", "device:A7")
print(d.find("phone:555-0100") == d.find("device:A7"))  # True