Faangprep Logo
Log inStart free
Browse curriculum

Optimized Union-Find

Optimized union-find uses path compression and union by rank to flatten the tree structure, achieving nearly constant time per operation.

Every set is a tree, and its root is the set's name — so "are these two connected?" is "do they climb to the same node?". The cost of that question is the height of the tree, and the two settings below are the only reason it stays small. Turn both off and watch Height pass 3.

READY

parent

0

0

1

1

2

2

3

3

4

4

5

5

6

6

7

7

depth

0

0
1
2
3
4
5
6
7

Sets

8

Height

0

Bound

3

 

8 sets of one. parent[i] = i everywhere, so every node is its own root and every find costs a single read.

 

A

0

B

1

Merge

Path

Intuition

The naive Union-Find can degrade into a tall tree (like a linked list), making searching slow. We can fix this with two tricks:

1. Path Compression: When finding the leader, make every node on the path point directly to the leader. Next time, the lookup is instant.

2. Union by Rank: Always attach the shorter tree to the taller tree. This keeps the combined tree height minimal.

Concept

Optimizations:

  • Path Compression: During find(x), set parent[x] = find(parent[x]). This flattens the path.
  • Union by Rank: Track tree height (rank). If rank[rootX] > rank[rootY], parent[rootY] = rootX. If equal, increment rank of new root.

How it Works

Toggle the optimizations in the visualizer to see the difference!

  1. Without Optimizations: Trees can get very deep.
  2. With Path Compression: After a Find operation, all nodes on the path jump to the root.
  3. With Union by Rank: Trees tend to look broad and shallow "bushes" rather than tall "spines".

Step-by-Step Breakdown

1. Find(x): If parent[x] != x, recursively call find and update parent[x] with the result. Return parent[x].

2. Union(x, y): Find roots. Compare ranks. Attach smaller rank to larger rank. If equal, pick one and increment its rank.

When to Use

  • When you have millions of operations (N large, Q large).
  • MST algorithms (Kruskal) where speed is critical.
  • Dynamic graph connectivity.

When NOT to Use

  • If you need to reconstruct the history of unions (Compression destroys history).

How to Identify

"Fastest way to group items", "Check if graph is fully connected", "Detect cycle in undirected graph".

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Introduction

Next

Introduction

Frequently Asked Questions

What is Path Compression?

A technique that makes the "Find" operation flash-flat by pointing every node in a path directly to the root.

What is Union by Rank/Size?

A technique that always attaches the smaller tree under the root of the larger tree to keep the overall structure flat and efficient.

What is the Amortized Complexity?

With both optimizations, DSU achieves near-constant time O(α(n)), where α is the Inverse Ackermann Function.