Union-find

Union-find tracks which nodes belong to the same group, with near-constant time find and union once path compression and union by rank are added. It answers connectivity questions as edges arrive.

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

Explain what find and union do and what the parent array means
Write union-find with path compression and union by rank
Spot the bug of comparing parents instead of roots

In practice

A few lines that show Union-find doing its job.

Python

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

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

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False          # already connected
        self.parent[rb] = ra
        return True

The common mistake

Watch for

Comparing parent[a] == parent[b] to test connectivity. Only the roots say whether two nodes share a set; always compare find(a) with find(b).

What to know first

Your roadmap puts these before Union-find, unless you already know them.

Graph representations

How it stays learned

Once a session shows you understand Union-find, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

Day 3First recall, while it is fresh
Day 7Second, a week on
Day 18Last, when it has settled

Previous in the module← Topological sort