Data Structures

Union-Find (DSU)

Merge disjoint sets and query connectivity almost in constant time.

TimeO(α(n)) per opSpaceO(n)CategoryData Structures

Visualize this — step by stepNo signup needed.

The Disjoint Set Union (Union-Find) structure keeps track of a partition of elements into non-overlapping sets. It supports two operations — `find(x)` (which set is x in?) and `unite(a, b)` (merge the two sets) — both nearly constant time with path compression and union by rank.

DSU powers Kruskal's minimum spanning tree, connectivity queries, and countless 'group things together' problems. The mental model is a forest: each element points to a parent, and the root represents the set.

AlgoLens draws the parent array as an actual forest of trees — when you call `unite`, you watch two trees merge, which is far clearer than a flat array of parent indices.

The code

union_find.cpp

#include <bits/stdc++.h>
using namespace std;

int parent[7];

int find(int x) {
    while (parent[x] != x) x = parent[x];
    return x;
}
void unite(int a, int b) {
    parent[find(a)] = find(b);
}

int main() {
    int n = 7;
    for (int i = 0; i < n; i++) parent[i] = i;
    int edges[5][2] = {{0,1},{1,2},{3,4},{5,6},{2,6}};
    for (auto& e : edges) unite(e[0], e[1]);
    for (int i = 0; i < n; i++) cout << find(i) << ' ';
    cout << '\n';
    return 0;
}

Open this in the visualizer

Now run your own Union-Find (DSU)

AlgoLens traces your code — arrays, graphs, trees and recursion — from a real execution, so you see how it actually behaves, not a canned animation.

Paste your code

Keep going

Linked List

Nodes connected by pointers — traversal and insertion made visible.

Stack and Queue

Last-in-first-out versus first-in-first-out, side by side.

Priority Queue (Binary Heap)

Always pop the largest — a tree hiding inside an array.

Prefix Sums

Precompute once, then answer any range sum with a single subtraction.