BeginnerGraphs

Union-Find (DSU)

Disjoint Set Union to maintain connectivity, Kruskal MST, and offline queries

Time: α(n)
Space: O(n)
Pattern Overview

Core Idea

Union by rank and path compression achieve near-constant-time connectivity operations.

When to Use

Use for dynamic connectivity, grouping by relations, and Kruskal's MST.

General Recognition Cues
General indicators that this pattern might be applicable
  • Connectivity queries
  • Merge groups
  • Kruskal MST
Pattern Variants & Approaches
Different methodologies and implementations for this pattern
1

Connectivity

Union and find with compression

When to Use This Variant
  • Same set?
Use Case
Dynamic connectivity
Advantages
  • Amortized inverse Ackermann
Implementation
class DSU:
    def __init__(self, n): self.p=list(range(n)); self.r=[0]*n
    def find(self, x):
        if self.p[x]!=x: self.p[x]=self.find(self.p[x])
        return self.p[x]
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra==rb: return False
        if self.r[ra]<self.r[rb]: ra,rb=rb,ra
        self.p[rb]=ra
        if self.r[ra]==self.r[rb]: self.r[ra]+=1
        return True
2

Kruskal MST

Sort edges and union if not connected

When to Use This Variant
  • Edge sort
Use Case
MST
Advantages
  • Greedy + DSU
  • Simple implementation
Implementation
def kruskal(n, edges):
    # edges: (w,u,v)
    dsu=DSU(n); edges.sort()
    cost=0; mst=[]
    for w,u,v in edges:
        if dsu.union(u,v): cost+=w; mst.append((u,v,w))
    return cost, mst
3

Offline Queries

Process queries/events with DSU

When to Use This Variant
  • Time-sorted queries
Use Case
Batch connectivity
Advantages
  • Flexible
Implementation
# Example: offline union queries sorted by edge weight (simplified placeholder)
def offline_connectivity(n, edges, queries):
    # edges: (w,u,v) sorted, queries: (w,u,v,idx) max weight allowed
    dsu=DSU(n); i=0; ans=[False]*len(queries)
    for w,u,v,idx in sorted(queries):
        while i<len(edges) and edges[i][0]<=w:
            _,a,b=edges[i]; dsu.union(a,b); i+=1
        ans[idx]= (dsu.find(u)==dsu.find(v))
    return ans
Common Pitfalls
Watch out for these common mistakes
  • Forgetting path compression
  • Not union by rank/size
  • Indexing mistakes
Code Templates
Compare implementations across different languages
def template(*args, **kwargs):
    # General template placeholder
    pass
Example Problems
Classic LeetCode problems using this pattern
Complexity Analysis
Time Complexity
α(n)

Inverse Ackermann per op.

Space Complexity
O(n)

Parents/rank arrays.

Ready to test your knowledge?

Test your pattern recognition with interactive questions