DSU

Disjoint Set Union with path compression and union by size in near-constant amortized time.

[Data Structures]|

Jul 9, 2026

|explanatory_notes.md|

#dsu#union-find#disjoint-set#path-compression

$cat source_code/

cpp

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

const int MAXN = 2e5 + 5;
int par[MAXN], rnk[MAXN];
int numComp;

void init(int n) {
    numComp = n;
    for (int i = 1; i <= n; i++) { par[i] = i; rnk[i] = 1; }
}

int find(int u) {
    return par[u] == u ? u : par[u] = find(par[u]);
}

bool same(int u, int v) { return find(u) == find(v); }

bool unite(int u, int v) {
    u = find(u); v = find(v);
    if (u == v) return false;
    if (rnk[u] < rnk[v]) swap(u, v);
    par[v] = u; rnk[u] += rnk[v];
    numComp--;
    return true;
}

int sz(int u) { return rnk[find(u)]; }
int components() { return numComp; }

29 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Disjoint Set Union (DSU)

Maintains disjoint sets with near-constant amortized operations.

Operations

find(u) — find the leader of

u

's set (with path compression)

unite(u, v) — merge sets containing

u

and

v

(union by size)

same(u, v) — check if

u

and

v

are in the same set

sz(u) — size of the set containing

u

components() — number of connected components

Optimizations

Path compression — every node on the find path points directly to root

Union by size — attach smaller tree under larger one

Combined: amortized

O(\alpha(n))

per operation, where

\alpha

is the inverse Ackermann function (effectively constant)

When to Use

Kruskal's MST, connectivity queries

Online edge additions with connectivity checks

Grouping elements dynamically

Complexity

Find / Unite —

O(\alpha(n))

amortized

Space —

O(n)