Union Find
Tracking connected groups.
Imagine people joining groups by shaking hands. Every handshake merges two groups into one. At any moment, you want to ask, are these two people in the same group? Union find answers that almost instantly.

- Handshakes merge groups
- Same group?
- Answered almost instantly
Union and find
Every person starts as their own group leader. Find follows parent links up to the leader of a group. It also shortens the path as it goes, so future finds are faster. Union finds both leaders, and makes one the parent of the other, merging the groups. Run it. After three handshakes, Ana and Dev are connected, but Eli is still alone.
class UnionFind:
def __init__(self, items):
self.parent = {x: x for x in items}
def find(self, x):
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
self.parent[ra] = rb
return True
uf = UnionFind(["Ana", "Ben", "Cara", "Dev", "Eli"])
uf.union("Ana", "Ben"); uf.union("Cara", "Dev"); uf.union("Ben", "Dev")
print(uf.find("Ana") == uf.find("Dev"))
print(uf.find("Ana") == uf.find("Eli"))True False
Union find facts
With path shortening, each operation is almost O of one, in practice. It's the go to tool for counting connected groups, merging accounts that share an email, and building networks cheaply, with an algorithm called Kruskal's. And union returning false tells you two things were already connected.
| key | value |
|---|---|
| find | who leads my group? |
| union | merge two groups |
| Cost | almost O(1) |
| Used for | groups, networks, Kruskal |
Summary
Union find tracks groups. Find gets the leader, and union merges two groups. Next, using it, and depth first search, to spot impossible plans.
Key takeaways- find(x)
- union(a, b)
- Path shortening