# π₯ Union find (disjoint set) in javascript

## π₯ Final implementation

``````class UnionFind {
constructor(n) {
this.root = Array(n)
.fill(null)
.map((_, i) => i);
this.rank = Array(n).fill(1);
this.components = n;
}

find(node) {
if (node === this.root[node]) return node;
return (this.root[node] = this.find(this.root[node]));
}

union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);

if (rootX === rootY) return false;

if (this.rank[rootX] < this.rank[rootY]) {
this.root[rootX] = rootY;
} else if (this.rank[rootX] > this.rank[rootY]) {
this.root[rootY] = rootX;
} else {
this.root[rootY] = rootX;
this.rank[rootX] += 1;
}
this.components -= 1;
return true;
}

connected(x, y) {
return this.find(x) === this.find(y);
}

getComponents() {
return this.components;
}
}
``````

## 1. Quick find

``````class UnionFind {
constructor(n) {
this.root = Array(n)
.fill(null)
.map((_, i) => i);
this.components = n;
}

find(node) {
// quick find
return this.root[node];
}

union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);

if (rootX === rootY) return true;

// rootY -> rootX
for (let i = 0; i < this.root.length; i += 1) {
if (this.root[i] === rootY) {
this.root[i] = rootX;
}
}
this.components -= 1;
return true;
}

connected(x, y) {
return this.find(x) === this.find(y);
}

getComponents() {
return this.components;
}
}
``````

## 2. Quick union

``````class UnionFind {
constructor(n) {
this.root = Array(n)
.fill(null)
.map((_, i) => i);
this.components = n;
}

find(node) {
while (node !== this.root[node]) {
node = this.root[node];
}
return node;
}

union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);

if (rootX === rootY) return true;

// quick union
this.root[rootY] = rootX;
this.components -= 1;
return true;
}

connected(x, y) {
return this.find(x) === this.find(y);
}

getComponents() {
return this.components;
}
}
``````

## 3. Union by rank

``````class UnionFind {
constructor(n) {
this.root = Array(n)
.fill(null)
.map((_, i) => i);
this.rank = Array(n).fill(1);
this.components = n;
}

find(node) {
while (node !== this.root[node]) {
node = this.root[node];
}
return node;
}

union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);

if (rootX === rootY) return false;

// union by rank
if (this.rank[rootX] < this.rank[rootY]) {
this.root[rootX] = rootY;
} else if (this.rank[rootX] > this.rank[rootY]) {
this.root[rootY] = rootX;
} else {
this.root[rootY] = rootX;
this.rank[rootX] += 1;
}
this.components -= 1;
return true;
}

connected(x, y) {
return this.find(x) === this.find(y);
}

getComponents() {
return this.components;
}
}
``````

## 4. Path compression

``````class UnionFind {
constructor(n) {
this.root = Array(n)
.fill(null)
.map((_, i) => i);
this.rank = Array(n).fill(1);
this.components = n;
}

find(node) {
if (node === this.root[node]) return node;
// path compression
return (this.root[node] = this.find(this.root[node]));
}

union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);

if (rootX === rootY) return false;

if (this.rank[rootX] < this.rank[rootY]) {
this.root[rootX] = rootY;
} else if (this.rank[rootX] > this.rank[rootY]) {
this.root[rootY] = rootX;
} else {
this.root[rootY] = rootX;
this.rank[rootX] += 1;
}
this.components -= 1;
return true;
}

connected(x, y) {
return this.find(x) === this.find(y);
}

getComponents() {
return this.components;
}
}
``````