Union-Find (DSU) visualizer: path compression, union by rank, live forest view, parent/rank/size arrays and C++ template. Step-through or manual mode.
A Disjoint Set Union keeps track of which nodes belong to the same connected component. You can merge two components with union(a, b) and ask whether two nodes share a root with find(a), both running in near-constant time. Two optimisations make that possible: union by rank attaches the shallower tree under the deeper one so trees never grow tall, and path compression rewires every visited node directly to the root on the way back from a find, so future lookups become a single hop.
The visualizer colours each component a distinct shade, marks roots with an R badge, and keeps the parent[], rank[] and size[] arrays live on screen. The generated C++ template uses the layout competitive programmers paste into their contest environment without modification.
union 0 1 merges two components, find 3 traces to the root. Press Load Sample to insert the lead sequence.Without any optimisation, repeated unions can build a chain of n nodes and find takes O(n). Union by rank keeps the tree height at most O(log n) by always attaching the shorter tree under the taller one, only incrementing the rank when two equal-rank roots merge. Path compression then reduces future find calls to O(1) amortised: every node visited during a find is reattached directly to the root, so the next call on any of those nodes terminates in one step. Together the two give O(m alpha(n)) for m operations on n nodes, where alpha(n) is the inverse Ackermann function, effectively constant for any n that fits in 64-bit memory.
The lead Load Sample sequence demonstrates both in eight operations: four pair-unions build components {0,1} and {2,3} and {4,5} and {6,7}, two chain-unions merge each pair, then union 3 4 collapses all eight nodes into one component, and find 7 path-compresses the remaining chain depth to at most 1 for every visited node.
union(0, 1) three times yields the same state as calling it once. The step label reads “already in same set” for the second and third calls, which is the exact behaviour Kruskal's MST loop relies on.union 3 9 on an 8-node DSU returns the error “Node index out of range [0, 7]: "union 3 9"” and stops processing so no later step runs against a corrupt state.MAXN to whatever the problem allows.Forest — each color is a component
R = root of its component · hover a node for details
parent[]
rank[]
size[]
C++ Template (path compression + union by rank)
// DSU / Union-Find — generated by UtilityToolsLab
// Nodes: 8 | Path compression + Union by rank
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100001;
int parent[MAXN], rnk[MAXN], sz[MAXN];
void init(int n) {
for (int i = 0; i < n; i++) parent[i] = i, rnk[i] = 0, sz[i] = 1;
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]); // path compression
return parent[x];
}
// Returns true if a merge happened
bool unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return false;
if (rnk[a] < rnk[b]) swap(a, b); // a has higher rank
parent[b] = a;
sz[a] += sz[b];
if (rnk[a] == rnk[b]) rnk[a]++;
return true;
}
bool connected(int a, int b) { return find(a) == find(b); }
int componentSize(int x) { return sz[find(x)]; }
int main() {
int n = 8;
init(n);
// Example operations matching the visualizer
// unite(0, 1);
// unite(2, 3);
// unite(0, 2);
// cout << find(3) << "\n"; // → root of the merged component
// cout << connected(1, 3) << "\n"; // 1
// cout << componentSize(1) << "\n"; // 4
}