Union Find data structure. Both simple with no optimizations and optimized Union Find with Path Compression/Collapsing Find and Union by Rank

union-find.js

class UnionFind {
	constructor(size) {
		this.nodes = new Array(size).fill(-1)
	}

	find(i) {
		while(true) {
			if(i === this.nodes[i]) this.nodes[i] = -1
			if(this.nodes[i] < 0) {
				return i;
			}
			i = this.nodes[i]
		}
	}

	union(p, q) {
		
		let pParent = this.find(p)
		let qParent = this.find(q)

		// this.nodes[pParent] = qParent;
		this.nodes[qParent] = pParent;
	}
}

class UnionFindOptimized extends UnionFind {
	constructor(size) {
		super(size)
	}
	
	//Recursive version of find(). Implements Path Compression/Collapsing Find
	find(i) {
		if(i === this.nodes[i]) this.nodes[i] = -1;
		if(this.nodes[i] < 0) return i;
		
		let parent = this.find(this.nodes[i])
		this.nodes[i] = parent;
		return parent;
	}

	//Iterative Path Compression or Collapsing Find
	find(i) {
		//keep track of our "path" as we look for our ulitmate parent
		let stack = []
		while(true) {
			if(i === this.nodes[i]) this.nodes[i] = -1
			if(this.nodes[i] < 0) {
				
				this.nodes[i] -= stack.length;

				while(stack.length > 0) {
					this.nodes[stack.pop()] = i
				}

				
				return i;
			}
			stack.push(i)
			i = this.nodes[i]
		}
	}

	union(p, q) {
		let pParent = this.find(p)
		let qParent = this.find(q)

		//Remember a negative number indicates it is a parent
		//So the minimum actually means greater rank.
		let lowerRank  = Math.max(pParent, qParent)
		let higherRank = Math.min(pParent, qParent)

		//Increase the magnitude of the current higher rank.
		this.nodes[higherRank] += this.nodes[lowerRank]
		this.nodes[lowerRank] = higherRank;

	}
}