Disjoint set union with path compression and union by rank
When to useConnected components, redundant connection, account merge, dynamic connectivity
iterative
Introduction to Minimum Spanning Tree
mst_introMerge User Accounts
dsu_account_mergeUnion Find | Disjoint Set Union Data Structure Introduction
dsu_introUnion Find | Disjoint Set Union Introductory Problem
dsu_problem_introUnion Find | Disjoint Set Union | Set Size
dsu_set_sizeMin Cost To Add New Roads
min_cost_to_add_new_roadsMinimum Cost to Connect All Nodes (Minimum Spanning Tree I)
min_cost_to_connect_all_nodesMin Cost to Repair Edges (Minimum Spanning Tree II)
min_cost_to_repair_edgesMinimum Spanning Tree | Forests
mst_forestNumber of Connected Components
number_of_connected_componentsGraph Valid Treemedium
graph_valid_tree · no slotsINITIALIZE
parent[i] = i; rank[i] = 0
const parent = new Array(n);for (let i = 0; i < n; i++) parent[i] = i;
const dsu = new DSU();const emailToName = new Map();
this.parent[i] = i; this.rank[i] = 0; // for all i in [0, n)
this.parent = new Map(); // each element maps to itself on first find
this.parent = new Map(); this.size = new Map(); // size[x] = 1 on first find
const parent = Array(n+1).map((_, i) => i); // + find closure, cost=0, edges=0
const parent = new Array(n + 1);for (let i = 0; i <= n; i++) parent[i] = i;
const parent = new Array(n + 1).fill(0).map((_, i) => i);const find = (x) => { if (parent[x] !== x) parent[x] = find(parent[x]); return parent[x]; };
const parent = new Array(n);for (let i = 0; i < n; i++) parent[i] = i;
const parent = new Array(n).fill(0).map((_, i) => i);const find = (x) => { if (parent[x] !== x) parent[x] = find(parent[x]); return parent[x]; };let count = n;
—
find/union
find compresses path; union links by rank
function find(x) { while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }function union(a, b) { const ra = find(a), rb = find(b); if (ra === rb) return false; parent[ra] = rb; return true; }
—
find: walk parent[x] until root (path halving); union: attach smaller rank under larger
find: recursive path compression; new elements initialized lazily in find
find: lazy init with size=1; path compression; size lives at root
find: recursive path compression; union: parent[rootA] = rootB
function find(x) { while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }function union(a, b) { const ra = find(a), rb = find(b); if (ra === rb) return false; parent[ra] = rb; return true; }
// find is defined inline above; union done inline in traversal
function find(x) { while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }function union(a, b) { const ra = find(a), rb = find(b); if (ra === rb) return false; parent[ra] = rb; return true; }
// find is defined inline above; union done inline in traversal
—
TRAVERSE
iterate edges/relationships
const sorted = [...edges].sort((a, b) => a[2] - b[2]);for (const [u, v, w] of sorted) {
for (const account of accounts) {
// operations arrive one at a time — find/union called directly
// operations arrive as merge(x,y) or isSame(x,y) calls
// operations arrive as merge(x,y) or count(x) calls
connections.sort((a,b) => a[2]-b[2]); for (const [a,b,c] of connections) {
const sorted = [...newEdges].sort((a, b) => a[2] - b[2]);for (const [u, v, c] of sorted) {
edgesToRepair.sort((a, b) => a[2] - b[2]);for (const [a, b, c] of edgesToRepair) {
const sorted = [...edges].sort((a, b) => a[2] - b[2]);for (const [u, v, w] of sorted) {
for (const [a, b] of connections) {
—
[UNION]
union endpoints (or check connectivity)
if (union(u, v)) { total += w; used++; if (used === n - 1) break; }
emailToName.set(account[i], name);dsu.union(account[1], account[i]);
this.parent[ry] = rx; this.rank[rx] += 1; // union by rank
this.parent.set(rootX, rootY); // or: return this.find(x) === this.find(y)
this.parent.set(rootX, rootY); this.size.set(rootY, sizeY + sizeX);
if (rootA !== rootB) { parent[rootA] = rootB; cost += c; edges++; }
if (union(u, v)) cost += c;
const rootA = find(a), rootB = find(b);if (rootA !== rootB) { parent[rootA] = rootB; cost += c; }
if (union(u, v)) total += w;
const rootA = find(a), rootB = find(b);if (rootA !== rootB) { parent[rootA] = rootB; count--; }result.push(count);
—
RETURN
count distinct roots or query specific connectivity
return total;
return result;
return rx === ry; // true if same component (find returns root)
return this.find(x) === this.find(y); // isSame check
return this.size.get(this.find(x)); // cluster size at root
return edges === n - 1 ? cost : -1;
return cost;
return cost;
return total;
return result;
—