DAA Greedy Tools 25

Union-Find (Disjoint Set Union)

Visualize MakeSet, Find, Union with path compression and union by rank.

← Index

DSU Visualizer (Plotly)

Speed
Elements: 0..n-1
Script shows unions + finds + compression.
Used in Manual mode or override demo inputs.
Highlights path; compression updates shown.
Path Compression Union by Rank
Sets (roots)
—
Operations done
0
Current action
Idle
parent[]
Roots point to themselves.
rank[]
Used in union-by-rank.
Find path
Visited nodes (x → … → root).
Pseudocode (DSU)
Line: —

Step Explanation

Click Start to initialize parent[i]=i, rank[i]=0. Then use Step or manual buttons.

Key ideas & complexity
  • Find(x) returns the representative (root) of x’s set.
  • Path compression flattens trees during Find → faster later operations.
  • Union by rank avoids tall trees by attaching smaller rank under larger.
  • With both, DSU is amortized ~ O(α(n)) per operation.

Course designed by Abhay Singh Bisht. Connect on LinkedIn →