AI Hints
Home›DSA in Python Tutorial›Groups and Cycles
DSA in Python · Lesson 85 of 132

Union Find

Tracking connected groups.

⏱ 2 min read▶ Video at 1:41:09🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Union Find
From the video: Union Find
  • 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.

union_find.pypython
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"))
Output
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.

keyvalue
findwho leads my group?
unionmerge two groups
Costalmost O(1)
Used forgroups, 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
Next up: Practice: Course Schedule — can you finish every course?