Fundamentals/Patterns/Union Find (DSU)11 problems· Graph

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_intro
Merge User Accounts
dsu_account_merge
Union Find | Disjoint Set Union Data Structure Introduction
dsu_intro
Union Find | Disjoint Set Union Introductory Problem
dsu_problem_intro
Union Find | Disjoint Set Union | Set Size
dsu_set_size
Min Cost To Add New Roads
min_cost_to_add_new_roads
Minimum Cost to Connect All Nodes (Minimum Spanning Tree I)
min_cost_to_connect_all_nodes
Min Cost to Repair Edges (Minimum Spanning Tree II)
min_cost_to_repair_edges
Minimum Spanning Tree | Forests
mst_forest
Number of Connected Components
number_of_connected_components
Graph Valid Treemedium
graph_valid_tree · no slots
INITIALIZE
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;