Preset

Nodes (n)

Operation

Build three pairs, query connectivity, then merge components with union(1,2).

union(0, 1)union(2, 3)union(4, 5)connected(0, 1)connected(0, 2)union(1, 2)connected(0, 3)

SPEED

INIT

Initialized 8 disjoint sets — each node is its own parent (parent[i] = i), rank[i] = 0.

Sets

Find hops

Step

1/44

Active / path Compressed edgeColors = component membership

parent[] & rank[]

i	0	1	2	3	4	5	6	7
parent	0	1	2	3	4	5	6	7
rank	0	0	0	0	0	0	0	0

unionFind.js

1class UnionFind {

2 constructor(n) {

3 this.parent = Array(n).fill(0).map((_, i) => i);

4 this.rank = Array(n).fill(0);

5 }

7 find(x) {

8 if (this.parent[x] !== x) {

9 this.parent[x] = this.find(this.parent[x]); // compress

10 }

11 return this.parent[x];

12 }

14 union(x, y) {

15 const rx = this.find(x), ry = this.find(y);

16 if (rx === ry) return;

17 if (this.rank[rx] < this.rank[ry]) {

18 this.parent[rx] = ry;

19 } else if (this.rank[rx] > this.rank[ry]) {

20 this.parent[ry] = rx;

21 } else {

22 this.parent[ry] = rx;

23 this.rank[rx]++;

24 }

25 }

27 connected(x, y) {

28 return this.find(x) === this.find(y);

29 }

30}

About the Union-Find (DSU) algorithm

Disjoint Set Union with path compression and union by rank. Near-constant time connectivity queries.

Category: Data Structures
Difficulty: Medium
Time complexity: O(α(n)) amortized
Space complexity: O(n)