Union-Find (Disjoint Set)

[!NOTE] How do you keep track of who is friends with whom in a massive social network? Or if two computers are connected in a network? Enter the Union-Find data structure.

1. The Concept: Dynamic Connectivity

We have a set of elements (nodes). We want to perform two operations efficiently:

  1. Union(A, B): Connect A and B (merge their sets).
  2. Find(A): Determine which set A belongs to.

If Find(A) == Find(B), then A and B are connected.

  1. Path Compression: When finding the root of a node, point it directly to the root so future lookups are faster. This flattens the tree.
  2. Union by Rank: Always attach the shorter tree to the taller tree to keep the height logarithmic.

The Complexity: Inverse Ackermann Function α(N)

With both optimizations, amortized time per operation is O(α(N)).

  • What is α? It is the inverse of the Ackermann function, which grows so fast that for any N smaller than the number of atoms in the universe, α(N) < 5.
  • Practical terms: It is essentially Constant Time for all realistic inputs.

2. Interactive: Social Circles

Click on two people to introduce them (Union). Watch how their groups merge. The colors represent the distinct sets (Connected Components).

Sets: 8
Click Node A then Node B to Union them.

3. Code Implementation: Union-Find

Java

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

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

  public int find(int i) {
    if (parent[i] != i) {
      parent[i] = find(parent[i]); // Path Compression
    }
    return parent[i];
  }

  public void union(int i, int j) {
    int rootI = find(i);
    int rootJ = find(j);

    if (rootI != rootJ) {
      // Union by Rank
      if (rank[rootI] < rank[rootJ]) {
        parent[rootI] = rootJ;
      } else if (rank[rootI] > rank[rootJ]) {
        parent[rootJ] = rootI;
      } else {
        parent[rootI] = rootJ;
        rank[rootJ]++;
      }
    }
  }
}

Go

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

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

func (uf *UnionFind) Find(i int) int {
  if uf.parent[i] != i {
    uf.parent[i] = uf.Find(uf.parent[i]) // Path Compression
  }
  return uf.parent[i]
}

func (uf *UnionFind) Union(i, j int) {
  rootI := uf.Find(i)
  rootJ := uf.Find(j)

  if rootI != rootJ {
    if uf.rank[rootI] < uf.rank[rootJ] {
      uf.parent[rootI] = rootJ
    } else if uf.rank[rootI] > uf.rank[rootJ] {
      uf.parent[rootJ] = rootI
    } else {
      uf.parent[rootI] = rootJ
      uf.rank[rootJ]++
    }
  }
}

4. Deep Dive Strategy Lab: Union Find

Intuition Through Analogy

Think of this chapter like city route planning. The goal is not to memorize a fixed trick, but to repeatedly answer:

  1. What is the bottleneck?
  2. Which constraint dominates (time, memory, latency, correctness)?
  3. Which representation makes the bottleneck easier to eliminate?