DSA Union Find

Union Find, known as Disjoint Set Union, tracks which items belong to the same group. The structure answers two questions very quickly. Which group does an item belong to? Can two groups merge into one?

Imagine a school event where students arrive alone. Each student starts as a group of one. As friendships form, small groups merge into larger groups. Later, someone asks whether Maya and Leo belong to the same circle of friends. Union Find answers instantly.

The Two Operations

• Find returns the leader of a group. Two items with the same leader sit in the same group.
• Union merges two groups by connecting their leaders.

How It Stores Data

A parent array holds one entry per item. Each entry points to the item's parent. A leader points to itself.

Index:   0  1  2  3  4
Parent: [0, 1, 2, 3, 4]

Every item is its own leader at the start.

A Basic Version

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))

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

    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a != root_b:
            self.parent[root_b] = root_a

Watching Groups Merge

Start:        0   1   2   3   4

union(0, 1):  0   2   3   4
              |
              1

union(2, 3):  0   2   4
              |   |
              1   3

union(1, 3):  0   4
             / \
            1   2
                |
                3

After the last merge, items 0, 1, 2, and 3 share leader 0. Item 4 stays alone.

Problem: Long Chains

Repeated unions can build a tall chain such as 4 to 3 to 2 to 1 to 0. A find call on item 4 climbs four steps. Two improvements keep the chains short.

Improvement 1: Path Compression

During a find, every item on the climb gets attached directly to the leader. Future finds on those items take one step.

def find(self, x):
    if self.parent[x] != x:
        self.parent[x] = self.find(self.parent[x])
    return self.parent[x]

Before find(4):     After find(4):

 0                    0
 |                  / | \ \
 1                 1  2  3  4
 |
 2
 |
 3
 |
 4

Improvement 2: Union by Rank

Rank estimates the height of a group's tree. A union attaches the shorter tree under the taller tree. The taller tree keeps its height, and the structure stays flat.

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a == root_b:
            return False
        if self.rank[root_a] < self.rank[root_b]:
            root_a, root_b = root_b, root_a
        self.parent[root_b] = root_a
        if self.rank[root_a] == self.rank[root_b]:
            self.rank[root_a] += 1
        return True

With both improvements, each operation takes nearly constant time, written as O(α(n)). The value α(n) grows so slowly that it stays below 5 for any practical input.

Example: Count Friend Circles

def count_circles(people, friendships):
    uf = UnionFind(people)
    circles = people
    for a, b in friendships:
        if uf.union(a, b):
            circles -= 1
    return circles

print(count_circles(5, [(0, 1), (1, 2), (3, 4)]))   # 2

Each successful union merges two groups and lowers the circle count by one.

Where Union Find Helps

• Counting connected groups in a network.
• Detecting a cycle in an undirected graph.
• Building a minimum spanning tree with Kruskal's algorithm.
• Grouping similar items, such as accounts that share a detail.

Real-Life Uses

Social platforms group users who share mutual connections. Image tools label connected patches of pixels that touch each other. Network planners check whether every office connects to the main cable system. Each case boils down to the same question: do two items sit in the same group?

Common Mistakes

Skipping the find call before a union attaches the wrong nodes. Always compare group leaders, never the raw items. Forgetting path compression keeps the code correct but slow on large inputs. Print the parent array after each union on a small example to confirm the groups look right.

Time and Space Summary

The parent array and the rank array each hold n entries, so the space cost is O(n). Building the structure takes O(n) time. A basic version without improvements may spend O(n) on a single find. Path compression and union by rank together shrink the average cost to near constant time per operation.

Key Points

• Union Find manages groups that merge over time.
• Find returns a group leader, and union joins two groups.
• A parent array stores the structure.
• Path compression flattens the tree during find.
• Union by rank keeps trees short.
• Operations run in almost constant time.