Union Find

Union Find (Disjoint Set Union)

Use when: Dynamic connectivity, grouping nodes, cycle detection in undirected graphs.

Complexity: O(α(N)) per operation (nearly O(1))

Standard Implementation

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = n
 
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]
 
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # already connected
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px  # union by rank
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        self.components -= 1
        return True
 
    def connected(self, x, y):
        return self.find(x) == self.find(y)

Usage

uf = UnionFind(n)
 
for u, v in edges:
    uf.union(u, v)
 
# number of connected components
print(uf.components)
 
# check if two nodes are connected
print(uf.connected(0, n-1))

Cycle Detection (undirected graph)

def has_cycle(n, edges):
    uf = UnionFind(n)
    for u, v in edges:
        if not uf.union(u, v):  # already connected = cycle
            return True
    return False

Signals in a Problem

• “Number of connected components”
• “Are these nodes in the same group?”
• Cycle detection in undirected graph
• Kruskal’s MST algorithm