Code Templates

Master the Union-Find family of algorithms with these optimized code templates. Use them as starting points for solving connectivity, cycle detection, and minimum spanning tree problems. For a conceptual overview, check out the Union-Find Guide.

When to Use Union-Find

Union-Find is your go-to solution for dynamic connectivity problems where you need to:

Answer connectivity queries efficiently (
O(α(N))
amortized per operation)
Detect cycles in undirected graphs
Merge connected components incrementally
Build minimum spanning trees (Kruskal’s algorithm)
Solve problems involving equivalence relations

Key Characteristics:

Nearly
O(1)
operations after
O(N)
initialization
Path compression optimization makes repeated finds faster
Union by rank/size prevents tree height from growing
Ideal for offline queries where all union operations are known upfront

Common Applications:

Connected components (islands, provinces, friend circles)
Cycle detection (redundant connections, valid tree)
Minimum spanning tree (Kruskal’s algorithm)
Equivalence relations (equality equations)
Grid connectivity problems

Union-Find with Union by Rank

This is the standard Union-Find implementation with path compression and union by rank. Use this for most connectivity problems. After O(n) initialization, each find/union operation runs in amortized O(α(n)) time, which is practically constant.

When to Use:

Standard connectivity problems requiring component merging
Cycle detection in undirected graphs
Problems where elements need to be dynamically grouped
Any problem requiring efficient connectivity checks

Key Insight: find(x) returns root with path compression. union(x, y) merges by attaching smaller rank tree under larger one.

JavaScript:

class UnionFind {
    constructor(size) {
        this.parent = new Array(size);
        this.rank = new Array(size).fill(0);

        for (let i = 0; i < size; i++) {
            this.parent[i] = i;
        }
    }

    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }

    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);

        if (rootX !== rootY) {
            if (this.rank[rootX] < this.rank[rootY]) {
                this.parent[rootX] = rootY;
            } else if (this.rank[rootX] > this.rank[rootY]) {
                this.parent[rootY] = rootX;
            } else {
                this.parent[rootY] = rootX;
                this.rank[rootX]++;
            }
            return true;
        }
        return false;
    }

    connected(x, y) {
        return this.find(x) === this.find(y);
    }

    getComponents() {
        const seen = new Set();
        for (let i = 0; i < this.parent.length; i++) {
            seen.add(this.find(i));
        }
        return seen.size;
    }
}

Python:

class UnionFind:
    def __init__(self, size: int):
        self.parent = list(range(size))
        self.rank = [0] * size

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x != root_y:
            if self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            elif self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            else:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1
            return True
        return False

    def connected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    def get_components(self) -> int:
        roots = set(self.find(i) for i in range(len(self.parent)))
        return len(roots)

Java:

public class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            return true;
        }
        return false;
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }

    public int getComponents() {
        Set<Integer> roots = new HashSet<>();
        for (int i = 0; i < parent.length; i++) {
            roots.add(find(i));
        }
        return roots.size();
    }
}

C++:

#include <vector>
#include <unordered_set>

class UnionFind {
private:
    std::vector<int> parent;
    std::vector<int> rank;

public:
    UnionFind(int size) {
        parent.resize(size);
        rank.resize(size, 0);
        for (int i = 0; i < size; ++i) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    bool union_sets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            return true;
        }
        return false;
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }

    int getComponents() {
        std::unordered_set<int> roots;
        for (size_t i = 0; i < parent.size(); ++i) {
            roots.insert(find(i));
        }
        return roots.size();
    }
};

Go:

type UnionFind struct {
    parent []int
    rank   []int
}

func NewUnionFind(size int) *UnionFind {
    uf := &UnionFind{
        parent: make([]int, size),
        rank:   make([]int, size),
    }
    for i := 0; i < size; i++ {
        uf.parent[i] = i
    }
    return uf
}

func (uf *UnionFind) Find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.Find(uf.parent[x])
    }
    return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) bool {
    rootX := uf.Find(x)
    rootY := uf.Find(y)

    if rootX != rootY {
        if uf.rank[rootX] < uf.rank[rootY] {
            uf.parent[rootX] = rootY
        } else if uf.rank[rootX] > uf.rank[rootY] {
            uf.parent[rootY] = rootX
        } else {
            uf.parent[rootY] = rootX
            uf.rank[rootX]++
        }
        return true
    }
    return false
}

func (uf *UnionFind) Connected(x, y int) bool {
    return uf.Find(x) == uf.Find(y)
}

func (uf *UnionFind) GetComponents() int {
    roots := make(map[int]bool)
    for i := 0; i < len(uf.parent); i++ {
        roots[uf.Find(i)] = true
    }
    return len(roots)
}

Ruby:

class UnionFind
  def initialize(size)
    @parent = Array.new(size) { |i| i }
    @rank = Array.new(size, 0)
  end

  def find(x)
    if @parent[x] != x
      @parent[x] = find(@parent[x])
    end
    @parent[x]
  end

  def union(x, y)
    root_x = find(x)
    root_y = find(y)

    if root_x != root_y
      if @rank[root_x] < @rank[root_y]
        @parent[root_x] = root_y
      elsif @rank[root_x] > @rank[root_y]
        @parent[root_y] = root_x
      else
        @parent[root_y] = root_x
        @rank[root_x] += 1
      end
      return true
    end
    false
  end

  def connected(x, y)
    find(x) == find(y)
  end

  def get_components
    roots = Set.new
    (0...@parent.length).each do |i|
      roots.add(find(i))
    end
    roots.size
  end
end

Code Breakdown

The template relies on three critical components:

The Parent Array (parent):
- Initialize as parent[i] = i, each element is its own parent initially.
- find(x) traverses up the tree until reaching root (where parent[i] == i).
- Path compression updates nodes to point directly to root during traversal.
- Visual:
```
  graph TD
    subgraph "Before"
        B0[0] --> B1[1]
        B1 --> B2[Root 2]
    end

    subgraph "After"
        A0[0] --> A2[Root 2]
        A1[1] --> A2
    end

    style B2 fill:#f9f,stroke:#333
    style A2 fill:#9f9,stroke:#333
```
The Rank Array (rank):
- Tracks approximate height of each tree.
- During union, attach shorter tree under taller tree.
- When ranks are equal, arbitrarily choose one as parent and increment its rank.
- This prevents trees from becoming tall and unbalanced.
Path Compression:
- In find(x), recursively traverse up to root.
- After finding root, update parent[x] directly to root.
- Subsequent finds for x or nodes on path become
  O(1)
  .

Space vs Time Trade-off:

Construction: Costs
O(N)
time and space once.
Operations: Cost amortized
O(α(N))
, nearly constant.
Perfect for high-operation-count scenarios with repeated queries.

Union-Find with Union by Size

An alternative to union by rank. Instead of tracking height, track the size of each component. Always attach smaller component under larger one. This is useful when you need to track component sizes or find the largest component.

Key Differences from Rank-based:

Uses size array instead of rank.
During union, compare sizes instead of ranks.
Update size: size[root] += size[other_root].
Provides getSize(x) method to get component size.

JavaScript:

class UnionFindSize {
    constructor(size) {
        this.parent = new Array(size);
        this.size = new Array(size).fill(1);
        for (let i = 0; i < size; i++) {
            this.parent[i] = i;
        }
    }

    find(x) {
        if (this.parent[x] !== x) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }

    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);

        if (rootX !== rootY) {
            if (this.size[rootX] < this.size[rootY]) {
                this.parent[rootX] = rootY;
                this.size[rootY] += this.size[rootX];
            } else {
                this.parent[rootY] = rootX;
                this.size[rootX] += this.size[rootY];
            }
            return true;
        }
        return false;
    }

    getSize(x) {
        return this.size[this.find(x)];
    }

    connected(x, y) {
        return this.find(x) === this.find(y);
    }
}

Python:

class UnionFindSize:
    def __init__(self, size: int):
        self.parent = list(range(size))
        self.size = [1] * size

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x != root_y:
            if self.size[root_x] < self.size[root_y]:
                self.parent[root_x] = root_y
                self.size[root_y] += self.size[root_x]
            else:
                self.parent[root_y] = root_x
                self.size[root_x] += self.size[root_y]
            return True
        return False

    def get_size(self, x: int) -> int:
        return self.size[self.find(x)]

    def connected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

Java:

public class UnionFindSize {
    private int[] parent;
    private int[] size;

    public UnionFindSize(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            if (size[rootX] < size[rootY]) {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];
            } else {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
            }
            return true;
        }
        return false;
    }

    public int getSize(int x) {
        return size[find(x)];
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
}

C++:

#include <vector>

class UnionFindSize {
private:
    std::vector<int> parent;
    std::vector<int> size;

public:
    UnionFindSize(int n) {
        parent.resize(n);
        size.resize(n, 1);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    bool union_sets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            if (size[rootX] < size[rootY]) {
                parent[rootX] = rootY;
                size[rootY] += size[rootX];
            } else {
                parent[rootY] = rootX;
                size[rootX] += size[rootY];
            }
            return true;
        }
        return false;
    }

    int getSize(int x) {
        return size[find(x)];
    }

    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

Go:

type UnionFindSize struct {
    parent []int
    size   []int
}

func NewUnionFindSize(n int) *UnionFindSize {
    uf := &UnionFindSize{
        parent: make([]int, n),
        size:   make([]int, n),
    }
    for i := 0; i < n; i++ {
        uf.parent[i] = i
        uf.size[i] = 1
    }
    return uf
}

func (uf *UnionFindSize) Find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.Find(uf.parent[x])
    }
    return uf.parent[x]
}

func (uf *UnionFindSize) Union(x, y int) bool {
    rootX := uf.Find(x)
    rootY := uf.Find(y)

    if rootX != rootY {
        if uf.size[rootX] < uf.size[rootY] {
            uf.parent[rootX] = rootY
            uf.size[rootY] += uf.size[rootX]
        } else {
            uf.parent[rootY] = rootX
            uf.size[rootX] += uf.size[rootY]
        }
        return true
    }
    return false
}

func (uf *UnionFindSize) GetSize(x int) int {
    return uf.size[uf.Find(x)]
}

func (uf *UnionFindSize) Connected(x, y int) bool {
    return uf.Find(x) == uf.Find(y)
}

Ruby:

class UnionFindSize
  def initialize(size)
    @parent = Array.new(size) { |i| i }
    @size = Array.new(size, 1)
  end

  def find(x)
    if @parent[x] != x
      @parent[x] = find(@parent[x])
    end
    @parent[x]
  end

  def union(x, y)
    root_x = find(x)
    root_y = find(y)

    if root_x != root_y
      if @size[root_x] < @size[root_y]
        @parent[root_x] = root_y
        @size[root_y] += @size[root_x]
      else
        @parent[root_y] = root_x
        @size[root_x] += @size[root_y]
      end
      return true
    end
    false
  end

  def get_size(x)
    @size[find(x)]
  end

  def connected(x, y)
    find(x) == find(y)
  end
end

Variations

Basic Union-Find (No Optimizations)

For educational purposes or when N is very small. Without path compression and union by rank, find operations can degrade to

O(N)

in worst case.

Iterative Path Compression

Instead of recursive find, use iteration with two-pointer approach to avoid stack overflow for deep trees.

Weighted Union-Find

Store weights on edges for problems requiring relationship calculations (e.g., LeetCode 399 - Evaluate Division).

Persistent Union-Find

Maintains historical versions, useful for problems requiring undo operations or rollback.

Union-Find with Rollback

Supports reverting to previous state, useful in competitive programming with backtracking.

Next Steps

Now that you have templates, it’s time to apply them. Head over to the Practice Problems page to solve real LeetCode challenges using these patterns.