Disjoint set union

Use disjoint set union, or DSU, when groups merge and you repeatedly ask whether two items are in the same group. It is also called union-find.

Trace groups becoming connected

Start:       {0} {1} {2} {3} {4}
union(0, 1): {0, 1} {2} {3} {4}
union(2, 3): {0, 1} {2, 3} {4}
union(1, 3): {0, 1, 2, 3} {4}

One possible parent forest:
0 <- 1       4
^
2 <- 3

find(3): 3 -> 2 -> 0
compress: make 3 point directly to 0

Each item stores a parent. A root points to itself and represents its component. Two items are connected exactly when their roots are equal. The representative is an internal choice, not necessarily the smallest item.

The parent forest is not the original graph. Parent links summarize group membership; they do not describe actual roads or produce a path through the original edges.

Preserve two rules

Union by size attaches the smaller root below the larger root. Size is meaningful only at roots. Without compression, a node's depth rises only when its component at least doubles. Depth is therefore O(log n).

Path compression makes visited nodes point closer to the root during find. It changes the representation without changing group membership. Always find both roots before union; connecting arbitrary nodes can break the forest or lose part of a component.

Union returns false when both items already have the same root. In an undirected graph, an edge joining already-connected vertices closes a cycle.

Know the boundary

Initialization costs O(n) time and memory. With union by size and path compression, operations take O(α(n)) amortized time. The inverse Ackermann function α grows so slowly that this is effectively constant for practical sizes. It is still an amortized bound, not a promise that each find follows one link.

DSU supports merging, membership, and root summaries such as component size. It does not support arbitrary splitting or edge deletion. Removing a road may split a component, but the parent forest has discarded the evidence needed to decide that.

For a fixed graph, BFS or DFS can label all components in O(V + E). DSU is useful when edges arrive incrementally. More specialized offline methods can handle some deletion problems, but ordinary DSU cannot.

Predict and modify

1. After the trace, does find(4) change the number of groups?
2. Can you list a component's members by reading its root alone?
3. Track the largest component size after each successful union.

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

    def find(self, item):
        root = item
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[item] != item:
            previous_parent = self.parent[item]
            self.parent[item] = root
            item = previous_parent
        return root

    def union(self, left, right):
        left_root = self.find(left)
        right_root = self.find(right)
        if left_root == right_root:
            return False
        if self.size[left_root] < self.size[right_root]:
            left_root, right_root = right_root, left_root
        self.parent[right_root] = left_root
        self.size[left_root] += self.size[right_root]
        self.components -= 1
        return True


groups = DisjointSets(5)
assert groups.union(0, 1)
assert groups.union(2, 3)
assert groups.union(1, 3)
assert groups.find(0) == groups.find(3)
assert groups.find(0) != groups.find(4)
assert not groups.union(0, 3)
assert groups.size[groups.find(3)] == 4
assert groups.components == 2

Apply the failed-union check in Redundant Connection.

Next: Fenwick and segment trees.