Categories
Algorithms Javascript

Union Find in JS

Union Find is an algorithm that can be used to find disjoint sets, and cycles in a graph. Below are two implementations of this algorithm.

  1. Un-optimized
class UnionFind {
	// Time Complexity: find: O(n), union: O(n)
	constructor(n) {
		this.n = n;
		this.root = new Array(n).fill().map((v, i) => i);
	}
	find(node) {
		if (this.root[node] == node) return node;
		return (this.root[node] = this.find(this.root[node]));
	}
	union(a, b) {
		const u = this.find(a),
			v = this.find(b);
		if (u == v) return false; // Cycle
		this.root[u] = v;
	}
	disjointSets() {
		const set = new Set();
		for (let i = 0; i < this.n; i++) set.add(this.find(i));
		return set.size;
	}
}

2. Optimized (Ranked)

class UnionFind {
	// Time Complexity: find: O(n), union: O(n)
	constructor(n) {
		this.n = n;
		this.root = new Array(n).fill().map((v, i) => i);
		this.rank = new Array(n).fill(1);
	}
	find(node) {
		if (this.root[node] == node) return node;
		return (this.root[node] = this.find(this.root[node]));
	}
	union(a, b) {
		const u = this.find(a),
			v = this.find(b);
		if (u == v) return false;
		if (this.rank[u] > this.rank[v]) {
			this.root[v] = u;
			this.rank[u] += this.rank[v];
		} else {
			this.root[u] = v;
			this.rank[v] += this.rank[u];
		}
		return true;
	}
	disjointSets() {
		const set = new Set();
		for (let i = 0; i < this.n; i++) set.add(this.find(i));
		return set.size;
	}
}

Leave a Reply

Your email address will not be published. Required fields are marked *