← Graph Exploration

Micro-Drill #226 — Union-Find: init + find + union

Graph Exploration Target: 10s

Basic Union-Find without optimizations. find walks to root. union links roots. Returns False if already connected.

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

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

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return False
        self.parent[px] = py
        return True

Type it from memory. Go.

Practice Problems

← Micro #225 Micro #227 →