Skip to content

Union Find

First PublishedByAtif Alam

Difficulty: Medium. ROI: Low.

Other common names: Disjoint Set Union (DSU), disjoint sets, merge-find.

When to use: Use when you need to repeatedly merge sets and ask “are these two elements in the same set?” (e.g. connected components in an undirected graph, Kruskal’s MST, dynamic connectivity).

Idea: Each element has a parent; the representative (root) of a set is found by following parents. Union by rank (or size) and path compression keep operations nearly O(1) amortized.

Time / space: Nearly O(α(n)) per operation (inverse Ackermann). Space O(n) for parent/rank arrays.

Example #1 — Disjoint Set (Union Find)

Section titled “Example #1 — Disjoint Set (Union Find)”

Maintain disjoint sets with union and find. Each element has a parent; find follows parents to the root (representative). Union attaches the smaller tree under the larger (by rank); path compression in find keeps trees flat.

Sample input and output

uf = UnionFind(5)
uf.union(0, 1)
uf.union(1, 2)
print(uf.find(0) == uf.find(2))  # True (0, 1, 2 in same set)
print(uf.find(0) == uf.find(3))  # False
  • Sample input: 5 elements; union(0,1), union(1,2); then find(0), find(2), find(3).
  • Sample output: True, False — 0 and 2 share a set; 0 and 3 do not.

Code (with inline comments)

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))   # each element starts as its own parent (singleton set)
        self.rank = [0] * n            # approximate depth for union by rank


    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression: point to root
        return self.parent[x]


    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return   # already in same set
        if self.rank[px] < self.rank[py]:
            px, py = py, px   # attach smaller tree under larger
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1

Line-by-line:

  • self.parent = list(range(n)) — We have n elements 0..n-1. Each element’s “parent” starts as itself; following parents leads to a representative (root) for that set. Same root ⇒ same set.
  • self.rank = [0] * n — Rank is an upper bound on tree depth. When we merge two sets, we attach the smaller tree under the larger one (by rank) so the tree stays shallow.
  • find(x): If x is not its own parent, we recursively find the root of its parent and set parent[x] to that root (path compression). Next time we find(x) we get there in one step. Return the root.
  • union(x, y): Get roots px, py of x and y. If they’re the same, do nothing. Otherwise make the root of the smaller-rank tree point to the other root; if ranks are equal, increment one rank.

Execution trace (numbered list)

Initial: parent=[0,1,2,3,4], rank=[0,0,0,0,0].

  1. Step 1: union(0,1). find(0)=0, find(1)=1. Attach 1 under 0 → parent[1]=0, rank[0]=1.
  2. Step 2: union(1,2). find(1)=0, find(2)=2. Attach 2 under 0 → parent[2]=0.
  3. find(0)=0, find(2)=0 → same set (True). find(3)=3 → different set (False).

Execution trace (code with step comments)

uf = UnionFind(5)   # parent=[0,1,2,3,4], rank=[0,0,0,0,0]
uf.union(0, 1)      # find(0)=0, find(1)=1 → parent[1]=0, rank[0]=1
uf.union(1, 2)      # find(1)=0, find(2)=2 → parent[2]=0
# find(0)==find(2) → 0==0 → True
# find(0)==find(3) → 0==3 → False

Execution trace (ASCII diagram)

After union(0,1), union(1,2): 0 is the root; 1 and 2 point to 0.

Before:  0  1  2  3  4   (each its own set)
After union(0,1):  0←1  2  3  4
After union(1,2):  0←1  0←2  3  4   (0,1,2 same set)